一道很好的搜索题。WA一次，原因是二进制hash开的太小。 一般求最短步数的问题，大多采用BFS，当终点与当前节点的XY值相等时输出，本题也不例外。难点在于，镜子的状态如何处理。 注意到镜子的数目<10，每一镜子仅有两种状态 \ 和/ 。因此将每一面镜子左右视为0与1，得到二进制编码的值hash，存入BFS中的节点。最大节点状态为2^10*10*10=102400 ，时间和空间上完全满足要求。 这里总共有三个102400的数组。一个队列Q，一个step存放某节点的步数，一个sight进行预处理，记录下当镜子出于某种状态hash下，每个点是否能够访问。 代码太长，格式放不上来，辛辛苦苦打了半天没了，只好帖原文。里面有一些相当有用的技巧，比如对于每一面镜子i的开关操作（0置为1，1置为0）是2^i xor hash，又比如对方向的处理数组与处理函数——这就和马路边的城管一样，常见，而且实用。但是方向函数看代码是看不懂的，需要自己分析一下。 #include <cstdio>#include <string> char a[11][11];int N, M, num_m, num_b, step[10][10][1024], sight[10][10][1024], ans;int dir[4][2] ={ { 0, 1 }, { 1, 0 }, { 0, -1 }, { - 1, 0 }};int p[11] ={ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024}; typedef struct{ int x, y, dir, step, h;} Bat;Bat sb, eb, Mirror[12], Q[102410], B[100]; int init ();void bfs ();void proc ( int );int redir ( int, int, int );  //计算方向void print (); int main (){ //freopen ( "in.txt", "r", stdin ); while ( init () ) {  bfs ();  print (); } return 0;} int init (){ num_m = num_b = 0, ans = -1; if ( scanf ( "%d%d", &N, &M ) == EOF ) {  return 0; } gets ( a[0] ); int i, j;  for ( i = 0; i < N; i ++ ) {  gets ( a[i] );  for ( j = 0; j < M; j ++ )  {   //终始点   if ( a[i][j] == 'S' )   {    sb.x = i, sb.y = j, a[i][j] = '.';   }   if ( a[i][j] == 'E' )   {    eb.x = i, eb.y = j, a[i][j] = '.';   }   //镜子   if ( a[i][j] == '/' )   {    Mirror[num_m].x = i, Mirror[num_m].y = j, Mirror[num_m ++].dir = 0;   }   if ( a[i][j] == '\\' )   {    Mirror[num_m].x = i, Mirror[num_m].y = j, Mirror[num_m ++].dir = 1;   }   //蝙蝠   if ( a[i][j] == '>' )   {    B[num_b].x = i, B[num_b].y = j, B[num_b ++].dir = 0;   }   if ( a[i][j] == 'v' )   {    B[num_b].x = i, B[num_b].y = j, B[num_b ++].dir = 1;   }   if ( a[i][j] == '<' )   {    B[num_b].x = i, B[num_b].y = j, B[num_b ++].dir = 2;   }   if ( a[i][j] == '^' )   {    B[num_b].x = i, B[num_b].y = j, B[num_b ++].dir = 3;   }  } } //printf ( "%d %d\n", num_b, num_m ); memset ( step, 0xff, sizeof ( step ) ); memset ( sight, 0xff, sizeof ( sight ) ); return 1;} void bfs (){ //预处理所有的镜面反射状况 int hash = 0, i, j, k, tx, ty, td; for ( i = 0; i < num_m; i ++ ) {  hash += Mirror[i].dir ? p[i] : 0; } step[sb.x][sb.y][hash] = 0; //保存初始值 for ( k = 0; k < p[num_m]; k ++ ) {  proc ( k );  //处理镜面 p[num_m]种情况  for ( i = 0; i < N; i ++ )  {   for ( j = 0; j < M; j ++ )   {    if ( a[i][j] != '.' )    {     sight[i][j][k] = 0;    }   }  }  for ( i = 0; i < num_b; i ++ )  {   tx = B[i].x, ty = B[i].y, td = B[i].dir;   tx += dir[td][0], ty += dir[td][1];   while ( tx >= 0 && tx < N && ty >= 0 && ty < M && a[tx][ty] != '#' )   {    sight[tx][ty][k] = 0;    td = redir ( tx, ty, td );    tx += dir[td][0], ty += dir[td][1];   }  }  //pt ( k ); } //BFS int op, ed, tstep, th;  proc ( hash ); step[sb.x][sb.y][hash] = 0; if ( sight[sb.x][sb.y][hash] == 0 )  return; for ( op = -1, ed = 0, Q[0].x = sb.x, Q[0].y = sb.y, Q[0].step = 0, Q[0].h = hash; op ++ < ed; ) {  if ( Q[op].x == eb.x && Q[op].y == eb.y )  {   ans = Q[op].step;   break;  }  tstep = Q[op].step + 1, th = Q[op].h;  for ( i = 0; i < 4; i ++ )  {   tx = Q[op].x + dir[i][0], ty = Q[op].y + dir[i][1];   if ( tx >= 0 && tx < N && ty >= 0 && ty < M && sight[tx][ty][th] )   {    if ( step[tx][ty][th] == -1 )    {     step[tx][ty][th] = tstep;     Q[++ ed].x = tx, Q[ed].y = ty, Q[ed].h = th, Q[ed].step = tstep;    }   }  }  for ( i = 0; i < num_m; i ++ )  {   th = Q[op].h ^ p[i], tx = Q[op].x, ty = Q[op].y;   if ( sight[tx][ty][th] && step[tx][ty][th] == -1 )   {    step[tx][ty][th] = tstep;    Q[++ ed].x = tx, Q[ed].y = ty, Q[ed].h = th, Q[ed].step = tstep;   }  } }} void proc ( int hash ){ int i; int x = hash; for ( i = 0; i < num_m; i ++ ) {  Mirror[i].dir = hash & 1;  //printf ( "%d", Mirror[i].dir );  a[Mirror[i].x][Mirror[i].y] = Mirror[i].dir ? '\\' : '/';  hash >>= 1; } //pt ( x );} int redir ( int x, int y, int d ){ if ( a[x][y] == '/' ) {  return 3 - d; } if ( a[x][y] == '\\' ) {  return d ^ 1; } return d;} void print (){ if ( ans == -1 ) {  printf ( "poor\n" ); } else {  printf ( "%d\n", ans ); }}  

评论