一道很好的搜索题。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 );
}
}
评论