题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1175
越学越不会，BFS还是很高级的。
连连看
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 30994 Accepted Submission(s): 7694
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时，输入结束。
注意：询问之间无先后关系，都是针对当前状态的！
入数据有多组。每组数据的第一行有两个正整数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
Author
lwg
结题报告：
每个点可以多次走，那么我的vis[][]就要加一维vis[][][4]，这个点，是否从某一个方向走过。结构体不仅要x,y方位，还要有dire方向，turn 转过几次。一般这种要在某一定限制条件下的BFS，可以有个优化。
好题，好好揣摩。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std; const int MAXN = ;
int maps[MAXN][MAXN];
bool visited[MAXN][MAXN][];
int M, N;
const int to[][] = { { , }, { , }, { -, }, { , - } };
struct Node
{
int x, y;
int dire, turn;
}; void init()
{
for (int i = ; i <= N; i++)
{
for (int j = ; j <= M; j++)
{
scanf("%d", &maps[i][j]);
}
}
} bool BFS(int x1, int y1, int x2, int y2)
{
memset(visited, false, sizeof(visited));
queue<Node> que;
Node s;
s.x = x1;
s.y = y1;
s.dire = -;
s.turn = -;
que.push(s); for (int i = ; i < ; i++)
visited[x1][y1][i] = true; while (!que.empty())
{
Node u = que.front();
que.pop();
if (u.turn > )
continue;
for (int j = ; j < ; j++)
{
Node next;
next.turn = u.turn;
if (u.dire != j)
{
next.turn++;
}
for (int k = ;; k++)
{
next.x = u.x + to[j][] * k;
next.y = u.y + to[j][] * k;
if (next.x <= || next.y <= || next.x > N || next.y > M)
break;
if (next.x == x2 && next.y == y2)
{
if (next.turn <= )
{
return true;
}
}
if (maps[next.x][next.y] > || visited[next.x][next.y][j])
{
break;
}
next.dire = j;
que.push(next);
visited[next.x][next.y][j] = true;
}
}
}
return false;
} int main()
{
//freopen("input.txt", "r", stdin);
int Q, x1, y1, x2, y2;
while (scanf("%d%d", &N, &M) == )
{
if (N == && M == )
{
break;
}
init();
scanf("%d", &Q);
for (int i = ; i < Q; i++)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
if (!maps[x1][y1] || !maps[x2][y2] || maps[x1][y1] != maps[x2][y2])
{
puts("NO");
continue;
}
if (BFS(x1, y1, x2, y2))
{
puts("YES");
}
else
{
puts("NO");
}
}
}
return ;
}