Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 14847 Accepted Submission(s): 3880
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
1 #include<cstdio>
2 #include<cstdlib>
3 #include<deque>
4 #include<iostream>
5 #define maxn 1003
6 using namespace std;
7 int map[maxn][maxn];
8 int hash[maxn][maxn];
9 unsigned int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
10 int n,m;
11 struct node
12 {
13 int x,y;
14 int step,tag;
15 }start,end;
16 void save_map()
17 {
18 for(int i=1;i<=n;i++)
19 {
20 for(int j=1;j<=m;j++)
21 {
22 scanf("%d",&map[i][j]);
23 }
24 }
25 }
26
27 void bfs()
28 {
29 int i;
30 deque<node>q;
31 node q1,q2;
32 q.push_back(start);
33 for( i=1;i<=n;i++)
34 {
35 for(int j=1;j<=m;j++)
36 {
37 hash[i][j]=3;
38 }
39
40 }
41 while(!q.empty())
42 {
43 q1=q.front ();
44 q.pop_front();
45 for(i=0;i<4;i++)
46 {
47 q2.x=q1.x+dir[i][0];
48 q2.y=q1.y+dir[i][1];
49 q2.step=q1.step;
50 q2.tag=q1.tag;
51 if(q2.tag!=i)
52 {
53 q2.step++;
54 q2.tag=i;
55 }
56 if(q2.x==end.x&&q2.y==end.y&&q2.step<=2)
57 {
58 printf("YES\n");
59 return ;
60 }
61
62
63 if(q2.step<3&&q2.x>0&&q2.x<=n&&q2.y>0&&q2.y<=m&&map[q2.x][q2.y]==0)
64 {
65 if(hash[q2.x][q2.y]>=q2.step)
66 {
67 q.push_back(q2);
68 hash[q2.x][q2.y]=q2.step;
69 }
70 }
71
72 }
73 }
74 printf("NO\n");
75 }
76
77 int main()
78 {
79 int t,i;
80 while(scanf("%d%d",&n,&m),n+m)
81 {
82 save_map();
83 scanf("%d",&t);
84 for(i=0;i<t;i++)
85 {
86 scanf("%d %d %d %d",&start.x,&start.y,&end.x,&end.y);
87 start.step=-1;
88 start.tag=-1;
89 if(map[start.x][start.y]==map[end.x][end.y]&&map[start.x][start.y]!=0)
90 bfs();
91 else
92 printf("NO\n");
93 }
94 }
95 return 0;
96 }