模拟题。读懂题目,跟着题目模拟就可以了。需要注意的就是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;
}