HDU 1175 连连看【2011年11月14号更新】
http://acm.hdu.edu.cn/showproblem.php?pid=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
有用剪枝：
如果走到当前位置已经转弯2次，若当前位置与目标位置既不同行也不同列，果断剪掉
速度还不错：
#include <iostream>using namespace std;#define inf 0x3fffffff#define M 1001int r, c, sx, sy, ex, ey, wan[M][M];int map[M][M];int x_move[4] = {-1, 0, 1, 0};int y_move[4] = {0, 1, 0, -1};bool flag;void dfs (int x, int y, int dir){if (x == ex && y == ey && wan[x][y] <= 2){flag = true;return ;}if (wan[x][y] == 2 && x != ex && y != ey) //剪枝return ;if (wan[x][y] > 2) //剪枝return ;for (int i = 0; i < 4; i++){int tx = x + x_move[i];int ty = y + y_move[i];if (tx < 0 || ty < 0 || tx >= r || ty >= c)continue;if ((tx != ex || ty != ey) && map[tx][ty] != 0 || wan[tx][ty] < wan[x][y])continue;if (dir != -1 && dir != i && wan[tx][ty] < wan[x][y] + 1)continue;wan[tx][ty] = wan[x][y];if (dir != -1 && dir != i)wan[tx][ty]++;dfs (tx, ty, i);if (flag)return ;}}inline bool scan_d(int &num) // 加速输入外挂，纯粹复制模板{ char in; bool IsN=false; in=getchar(); if(in==EOF) return false; while(in!='-'&&(in<'0'||in>'9')) in=getchar(); if(in=='-'){ IsN=true;num=0;} else num=in-'0'; while(in=getchar(),in>='0'&&in<='9'){ num*=10,num+=in-'0'; } if(IsN) num=-num; return true;}int main(){int i, j, q;while (~scanf ("%d%d", &r, &c), (r||c)){for (i = 0; i < r; i++)for (j = 0; j < c; j++)scan_d (map[i][j]);scan_d (q);while (q--){scan_d (sx);scan_d (sy);scan_d (ex);scan_d (ey);sx--, sy--, ex--, ey--;if (map[sx][sy] == 0 || map[sx][sy] != map[ex][ey]){puts ("NO");continue;}for (i = 0; i < r; i++)for (j = 0; j < c; j++)wan[i][j] = inf;flag = false;wan[sx][sy] = 0;dfs (sx, sy, -1);if (flag)puts ("YES");else puts ("NO");}} return 0;}