模拟题。读懂题目,跟着题目模拟就可以了。需要注意的就是geometrical
distance是两点间的直线距离,我理解为行和列差值的和错了一次。
有趣的是此题数据只有找到宝藏的情况。
但是,为什么不再问问能不能出来呢。
# include <cstdio> # include <cstring> # define rep(x) for ( x = 1; x <= n; ++x ) const int go[4][2] = {0,1, 0,-1, 1,0, -1,0}; //E,W,S,N const int pgo[4][2] = {0,1, 0,-1, -1,0, 1,0}; //E,W,N,S prefer! const int inf = 2147483647; int n; int m[35][35]; bool circle; int x, y, tx, ty, time; int abs(int x) { return x > 0 ? x: -x; } int sqr(int x) { return x * x; } bool inside(int x, int y) { return (x > 0 && x <= n && y > 0 && y <= n); } bool better(int x, int y, int xx,int yy) { return sqr(x-tx)+sqr(y-ty) < sqr(xx-tx)+sqr(yy-ty); } void Init() { int i,j,k,l,p; char s[35]; rep(i) { scanf("%s", s+1); rep(j) if ( s[j] == 'E' ) m[i][j] = 0; else if ( s[j] == 'W' ) m[i][j] = 1; else if ( s[j] == 'S' ) m[i][j] = 2; else if ( s[j] == 'N' ) m[i][j] = 3; } x = y = 1; tx = ty = n; time = 0; circle = false; } int cnt = 0; int sec[103][5]; bool check() { int i; for ( i = 1; i < time; ++i ) if ( sec[i][0] == x && sec[i][1] == y && sec[i][2] == tx && sec[i][3] == ty && sec[i][4] == (time&3) ) { circle = true; return true; } sec[i][0] = x,sec[i][1] = y,sec[i][2]= tx, sec[i][3] = ty, sec[i][4]= (time&3); return false; } bool step() { int f1 = (m[x][y]+time)&3, f2 = (m[tx][ty]+time)&3; if ( x == tx && y == ty ) return true; if ( check() ) return false; int xx = x + go[f1][0]; int yy = y + go[f1][1]; if ( inside(xx,yy) ) x = xx, y = yy; //自动走 xx = x, yy = y; for ( int i = 0; i < 4; ++i ) //喜好行走 { if ( !inside(x + pgo[i][0], y + pgo[i][1]) ) continue; if ( better(x + pgo[i][0],y + pgo[i][1], xx, yy) ) xx = x + pgo[i][0], yy = y + pgo[i][1]; } x = xx, y = yy; int txx = tx + go[f2][0]; int tyy = ty + go[f2][1]; if ( inside(txx, tyy) ) tx = txx, ty = tyy; //宝藏走 ++time; return false; } int main() { int t = 0; while ( scanf("%d", &n), n ) { if ( ++t > 1 ) printf("\n"); Init(); printf("Case %d:\n", t); while ( time < 100 ) { if ( step() ) { printf("Get the treasure! At step %d.\n", time); break; } if ( circle ) { printf("Impossible. At step %d.\n", time); break; } if ( time == 99 ) printf("Not sure.\n"); } } return 0; }