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 |
|
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 |