连连看（HDOJ 1175）
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
Sample Output
YES NO NO NO NO YES
My Code
这题其实还可以剪枝，不过这样已经可以过了，我懒得继续剪了，搜索题其实一般dfs和bfs都可以做的，这题大家也可以试试dfs。
#include
#include
#include
using namespace std;
int n, m,t;
int a1, b1, a2, b2; //因为y1之类的变量名会函数冲突，所以我干脆改成了a1,b1这种
int dx[4] = { 1,0,-1,0 }; //方向
int dy[4] = { 0,1,0,-1 };
int map[1005][1005];
int v[1005][1005]; //线肯定不会交叉，标记一下，避免重复
struct node
{
int x, y;
int turn; //记录转弯次数
}s; //s是起始点
bool check(node p) //判断是否越界，是否有棋子挡住（除终点棋子）
{
if (p.x <= 0 || p.y <= 0)
return false;
if (p.x > n || p.y > m)
return false;
if(!map[p.x][p.y])
return true;
if (p.x == a2 && p.y == b2)
return true;
return false;
}
void bfs()
{
queueq;
node p, e;
memset(v, 0, sizeof(v)); //别忘了头文件，vs不加也能运行，我就经常忘。。。
s.turn = -1; //起点往任意方向都没有转弯
q.push(s); //起点入队，初始化要在入队前做
v[s.x][s.y] = 1;
while (!q.empty())
{
p = q.front();
q.pop();
//cout << p.x << ' ' << p.y << ' ' << p.turn << endl;
if (p.turn >= 2) continue; //转弯次数超了的，直接过
for (int i = 0; i < 4; i++)
{
e.x = p.x + dx[i];
e.y = p.y + dy[i];
e.turn = p.turn + 1;
//cout <> n >> m)
{
if (!n && !m)
break;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> map[i][j];
cin >> t;
while (t--)
{
cin >> a1 >> b1 >> a2 >> b2;
if(a1==a2&&b1==b2) //起点终点重合的不行
{
cout << "NO" << endl;
continue;
}
if (a1>n||a2>n||b1>m||b2>m) //越界的不行
{
cout << "NO" << endl;
continue;
}
if (map[a1][b1] != map[a2][b2]) //棋子要相同的
{
cout << "NO" << endl;
continue;
}
if (map[a1][b1] * map[a2][b2] == 0) //总得有棋子吧
{
cout << "NO" << endl;
continue;
}
s.x = a1;
s.y = b1;
bfs();
}
}
return 0;
}