连连看
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5613 Accepted Submission(s): 1455
Problem Description
“连
连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来
（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看，咨询了同学的意见，
连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过。
玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。
玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。
Input
输
入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000)，分别表示棋盘的行数与列数。在接
下来的n行中，每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子，正整数表示棋子的类型。接下来的一行是一个正整数
q(0<q<50)，表示下面有q次询问。在接下来的q行里，每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第
x2行y2列的棋子能不能消去。n=0,m=0时，输入结束。
注意：询问之间无先后关系，都是针对当前状态的！
注意：询问之间无先后关系，都是针对当前状态的！
Output
每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。
Sample Input
3 4
1 2 3 4
0 0 0 0
4 3 2 1
4
1 1 3 4
1 1 2 4
1 1 3 3
2 1 2 4
3 4
0 1 4 3
0 2 4 1
0 0 0 0
2
1 1 2 4
1 3 2 3
0 0
1 2 3 4
0 0 0 0
4 3 2 1
4
1 1 3 4
1 1 2 4
1 1 3 3
2 1 2 4
3 4
0 1 4 3
0 2 4 1
0 0 0 0
2
1 1 2 4
1 3 2 3
0 0
Sample Output
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
姑且能够算一道模拟题吧，计算两点能否通过不超过两次转弯的线相连，并且这条线路上不能够有阻挡物，刚开始的时候可以做一些判定来剪枝，比如是否为同一点，是否是同一图案以及是否有一点为0，即没有图案。
这道题将BFS做一点小小的变形，即每次让一个方向的可能点全部入对列，这样能够使得拐弯次数限制到最小，标记的变量要设四个方向，每次走过的点要标记两个方向，向前和向后，显然不可能再次走到这一点以相同的方向或者反过来。其他就和一般的BFS差不多了。
代码如下：
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#define INF 0x7f7f7f7f
using namespace std;
int map[1005][1005], hash[4][1005][1005], dir[4][2]= { 1, 0, -1, 0, 0, 1, 0, -1 };
struct Node
{
int x, y, type, ti, dir;
}info;
void gint( int &t )
{
char c;
while( c= getchar(), c< '0'|| c> '9' ) ;
t= c- '0';
while( c= getchar(), c>= '0'&& c<= '9' )
{
t= t* 10+ c- '0';
}
}
bool BFS( int sx, int sy, int ex, int ey )
{
queue< Node >q;
memset( hash, 0, sizeof( hash ) );
info.x= sx, info.y= sy, info.type= map[sx][sy], info.ti= 0, info.dir= -1;
hash[0][sx][sy]= hash[1][sx][sy]= hash[2][sx][sy]= hash[3][sx][sy]= 1;
q.push( info );
while( !q.empty() )
{
Node pos= q.front();
q.pop();
if( pos.x== ex&& pos.y== ey )
{
return true;
}
for( int i= 0; i< 4; ++i )
{
int x= pos.x+ dir[i][0], y=pos.y+ dir[i][1], ti= pos.ti, d= pos.dir;
while( ( map[x][y]== 0|| ( x== ex&& y== ey ) )&& !hash[i][x][y] )
{
int k= ( i== d|| d== -1 )? 0: 1;
info.x= x, info.y= y, info.ti= ti+ k, info.dir= i;
if( info.ti<= 2 )
{
if( info.ti< 2|| ( info.ti== 2 && ( x== ex|| y== ey ) ) )
{
q.push( info );
}
hash[i][x][y]= 1;
if( i== 0|| i== 1 )
{
hash[!i][x][y]= 1;
}
else if( i== 2 )
{
hash[3][x][y]= 1;
}
else
{
hash[2][x][y]= 1;
}
}
x+= dir[i][0], y+= dir[i][1];
}
}
}
return false;
}
int main()
{
int N, M;
while( scanf( "%d %d", &N, &M ), N| M )
{
memset( map, 0x7f, sizeof( map ) );
for( int i= 1; i<= N; ++i )
{
for( int j= 1; j<= M; ++j )
{
gint( map[i][j] );
}
}
int q;
scanf( "%d", &q );
while( q-- )
{
int sx, sy, ex, ey;
scanf( "%d %d %d %d", &sx, &sy, &ex, &ey );
if( ( map[sx][sy]!= map[ex][ey] )|| map[sx][sy]== 0|| map[ex][ey]== 0|| ( sx== ex&& sy== ey ) )
{
puts( "NO" );
continue;
}
printf( BFS( sx, sy, ex, ey )? "YES\n": "NO\n" );
}
}
return 0;
}