HDU 1175.连连看

连连看
Time Limit:10000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
SubmitStatus Practice HDU 1175

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

连连看游戏的后台实现

根据我们接触到的练练看游戏，可以确定一下规则：

要点击两个不同的位置
点击的两个位置应该是合法位置
点击的两个位置应该对应的是相应的棋子，并且不能有空白格
棋子间路径只能通过空白格，并且最多只能转过两个拐角

如同正常的BFS一样，只是每次拓展路径要拓展一条直线，记录下到该点转过的拐角，拓展3层(两个拐角)

判断目标点是否能到达即可

  1 /*
  2 By:OhYee
  3 Github:OhYee
  4 Email:oyohyee@oyohyee.com
  5 Blog:http://www.cnblogs.com/ohyee/
  6 
  7 かしこいかわいい？
  8 エリーチカ！
  9 要写出来Хорошо的代码哦~
 10 */
 11 
 12 #include <cstdio>
 13 #include <algorithm>
 14 #include <cstring>
 15 #include <cmath>
 16 #include <string>
 17 #include <iostream>
 18 #include <vector>
 19 #include <list>
 20 #include <queue>
 21 #include <stack>
 22 using namespace std;
 23 
 24 //DEBUG MODE
 25 #define debug 0
 26 
 27 //循环
 28 #define REP(n) for(int o=0;o<n;o++)
 29 
 30 const int maxn = 1005;
 31 
 32 int m,n;
 33 int Map[maxn][maxn];
 34 int dis[maxn][maxn];
 35 
 36 typedef pair<int,int> point;
 37 
 38 int BFS(int s1,int s2,int v1,int v2) {
 39     #define con1(nn) (nn<=0||nn>n) 
 40     #define con2(mm) (mm<=0||mm>m)
 41     //位置错误
 42     if(con1(s1) || con1(v1) || con2(s2) || con2(v2))
 43         return -1;
 44     //同一位置
 45     if(s1 == v1 && s2 == v2)
 46         return -1;
 47     //棋子不同 或 无棋子
 48     if(Map[s1][s2] != Map[v1][v2] || Map[s1][s2]==0)
 49         return -1;
 50 
 51     queue<point> Q;
 52     memset(dis,-1,sizeof(dis));
 53 
 54     Q.push(point(s1,s2));
 55     dis[s1][s2] = 0;
 56 
 57     while(!Q.empty()) {
 58         int th1 = Q.front().first;
 59         int th2 = Q.front().second;
 60         Q.pop();
 61 
 62         //达到终点
 63         if(th1 == v1 && th2 == v2)
 64             break;
 65 
 66         //拓展节点
 67         #define condition 
 68         (next1 > 0 && next1 <= n && next2 > 0 && next2 <= m 
 69         && (Map[next1][next2] == 0||(next1==v1 && next2==v2)))
 70 
 71         #define push 
 72         if(dis[next1][next2]==-1 && dis[th1][th2]<=2) {
 73             Q.push(point(next1,next2));
 74             dis[next1][next2] = dis[th1][th2] + 1;
 75         }
 76 
 77         int next1,next2;
 78         for(next1 = th1,next2 = th2 + 1;condition;next2++) {
 79             push;
 80         }
 81         for(next1 = th1 + 1,next2 = th2;condition;next1++) {
 82             push;
 83         }
 84         for(next1 = th1,next2 = th2 - 1;condition;next2--) {
 85             push;
 86         }
 87         for(next1 = th1 - 1,next2 = th2;condition;next1--) {
 88             push;
 89         }
 90 
 91     }
 92     return dis[v1][v2];
 93 }
 94 
 95 bool Do() {
 96     if(scanf("%d%d",&n,&m),n == 0 && m == 0)
 97         return false;
 98     for(int i = 1;i <= n;i++)
 99         for(int j = 1;j <= m;j++)
100             scanf("%d",&Map[i][j]);
101     int T;
102     scanf("%d",&T);
103     while(T--) {
104         int s1,s2,v1,v2;
105         scanf("%d%d%d%d",&s1,&s2,&v1,&v2);
106         printf("%s
",BFS(s1,s2,v1,v2)==-1?"NO":"YES");
107     }
108     return true;
109 }
110 
111 int main() {
112     while(Do());
113     return 0;
114 }