Submission #117741


Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <list>
#include <cassert>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define EPS 1e-9
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;

struct State {
	int i, y, x, lv; ll t;
	State(int i_, int y_, int x_, int lv_, ll t_):
		i(i_), y(y_), x(x_), lv(lv_), t(t_) { }
};
bool operator<(const State &a, const State &b) {
	return a.t > b.t;
}

const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};

string a[10][10];
bool vis[10][10][10][102];
pii staircases[10][2];
int enemylv[10][10][10];
int main() {
	int T, W, H, L;
	cin >> T >> W >> H >> L; L = min(L, 101);
	while(cin.get() != '\n') ;
	rep(i, T) rep(y, H) getline(cin, a[i][y]);
	mset(enemylv, 0x80);
	mset(staircases, -1);
	int si = -1, sy = -1, sx = -1, gi = -1, gy = -1, gx = -1;
	rep(i, T) rep(y, H) { rep(x, W) {
		char &c = a[i][y][x * 2], &d = a[i][y][x * 2 + 1];
		if(c == ' ') c = d = '#';
		if(c == '@') c = d = '=';
		if(c == '_') {
			staircases[i][0] = mp(y,x);
			c = d = '=';
		}else if(c == '-') {
			staircases[i][1] = mp(y,x);
			c = d = '=';
		}else if(c == 'K') {
			si = i, sy = y, sx = x;
			c = d = '=';
		}else if(c == '$') {
			if(i == T-1) gi = i, gy = y, gx = x;
			c = d = '=';
		}else if(c == 'H' || isdigit(c)) {
			int lv = 0;
			if(c == 'H') lv = 100;
			else lv = (c-'0') * 10 + (d-'0');
			enemylv[i][y][x] = lv;
			c = d = 'E';
		}
	} cerr << a[i][y] << endl; }
	staircases[si][1] = mp(-1, -1);

	ll r = INFL;
	mset(vis, 0);
	priority_queue<State> q;
	q.push(State(si, sy, sx, L, 0));
	while(!q.empty()) {
		State s = q.top(); q.pop();
		bool &visb = vis[s.i][s.y][s.x][s.lv];
		if(visb) continue;
		visb = true;
//		cerr << s.i << ", " << s.y << ", " << s.x << ", " << s.lv << ": " << s.t << endl;
		//王の指輪
		if(s.i == gi && s.y == gy && s.x == gx) {
			r = s.t;
			break;
		}
		//上り階段
		if(staircases[s.i][0] == mp(s.y,s.x)) {
			pii p = staircases[s.i+1][1];
			q.push(State(s.i+1, p.first, p.second, s.lv, s.t + 1));
		}
		//下り階段
		if(staircases[s.i][1] == mp(s.y,s.x)) {
			pii p = staircases[s.i-1][0];
			q.push(State(s.i-1, p.first, p.second, s.lv, s.t + 1));
		}
		rep(d, 4) {
			int yy = s.y + dy[d], xx = s.x + dx[d];
			if(yy<0||yy>=H||xx<0||xx>=W) continue;
			char c = a[s.i][yy][xx * 2];
			if(c == '#') continue;
			if(c == '=') {
				q.push(State(s.i, yy, xx, s.lv, s.t + 1));
			}else if(c == 'E') {
				int elv = enemylv[s.i][yy][xx];
				if(elv > s.lv) continue;
				int nlv = s.lv + (elv == s.lv);
				q.push(State(s.i, yy, xx, nlv, s.t + elv + 1));
			}else assert(0);
		}
	}
	if(r == INFL) puts("Impossible");
	else cout << r << endl;
	return 0;
}

Submission Info

Submission Time
Task G - King's Ring Tower
User anta
Language C++11 (GCC 4.8.1)
Score 100
Code Size 3773 Byte
Status AC
Exec Time 46 ms
Memory 924 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 16
Set Name Test Cases
All 00-sample, 10-ignore_stairs, 11-undying, 12-stairs_position, 20-min, 21-max, 30-xxx, 40-impossible, 41-impossible, 50-999, 51-999, 60-bosses, 70-kr_floor, 80-unavailable_down, 98-xxx, 99-xxx
Case Name Status Exec Time Memory
00-sample AC 23 ms 920 KB
10-ignore_stairs AC 24 ms 924 KB
11-undying AC 23 ms 920 KB
12-stairs_position AC 20 ms 804 KB
20-min AC 22 ms 916 KB
21-max AC 22 ms 916 KB
30-xxx AC 22 ms 924 KB
40-impossible AC 22 ms 924 KB
41-impossible AC 22 ms 916 KB
50-999 AC 22 ms 924 KB
51-999 AC 22 ms 844 KB
60-bosses AC 20 ms 920 KB
70-kr_floor AC 19 ms 916 KB
80-unavailable_down AC 21 ms 920 KB
98-xxx AC 28 ms 912 KB
99-xxx AC 46 ms 920 KB