1175 - 連連看
http://acm.hdu.edu.cn/showproblem.php?pid=1175
連連看
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7173 Accepted Submission(s): 1847
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
比較有意思的一道題，看到的第一眼我就想到了dfs，試著寫了一下，就是超時~~~后來加了一個vis數組，把題ac了，但是運行時間到3900MS+,很郁悶~~在網上搜了別人的代碼，看到一個剪枝，模仿了一下，果然牛X，直接降到了64MS~~
代碼如下：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 int map[1005][1005], N, M, x1, x2, y1, y2, flag;
6 int dx[] = {-1, 1, 0, 0};
7 int dy[] = {0, 0, -1, 1};
8 int vis[1005][1005];
9 void dfs(int x, int y, int count, int dir)
10 {
11 if(flag)
12 return;
13 if(count >= 3)
14 return;
15 if(x == x2 && y == y2)
16 {
17 flag = 1;
18 return;
19 }
20 if(x < 0 || y < 0 || x >= N || y >= M || map[x][y] != 0 || vis[x][y])
21 return;
22 if(count == 2)
23 {
24 if(!(dir==0&&y2==y&&x2<x||dir==1&&y2==y&&x2>x||dir==2&&y2<y&&x2==x||dir==3&&y2>y&&x2==x))
25 return;
26 }//很關鍵的剪枝，如果沒有時間會達到3906MS或者超時~~
27 vis[x][y] = 1;
28 for(int i = 0; i < 4; i++)
29 {
30 if(i == dir)
31 dfs(x + dx[i], y + dy[i], count, dir);
32 else
33 dfs(x + dx[i], y + dy[i], count+1, i);
34 }
35 vis[x][y] = 0;
36 }
37 int main()
38 {
39 int ornum;
40 while(scanf("%d%d", &N, &M) && (N || M))
41 {
42 for(int i = 0; i < N; i++)
43 for(int j = 0; j < M; j++)
44 scanf("%d", &map[i][j]);
45 scanf("%d", &ornum);
46 while(ornum--)
47 {
48 scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
49 x1--; x2--; y1--; y2--;
50 flag = 0;
51 if((x1 != x2 || y1 != y2) && map[x1][y1] == map[x2][y2] && map[x1][y1] != 0)
52 {
53 memset(vis, 0, sizeof(vis));
54 vis[x1][y1] = 1;
55 for(i = 0; i < 4; i++)
56 dfs(x1 + dx[i], y1 + dy[i], 0, i);
57 }
58 if(flag)
59 printf("YES\n");
60 else printf("NO\n");
61 }
62 }
63 return 0;
64 }
還看到有人用bfs寫的，很仰慕，也用bfs寫了一下，但是一直過不了，看了好長時間沒看出來哪錯了，郁悶~~~
我把我wa的bfs代碼發上來，求指導~~
bfs。wa
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 using namespace std;
6 typedef struct node
7 {
8 int x, y;
9 int count;
10 int dir;
11 }State;
12 queue<State> q;
13 State begin;
14 int map[1005][1005], N, M, x1, x2, y1, y2, flag;
15 int dx[] = {-1, 1, 0, 0};
16 int dy[] = {0, 0, -1, 1};
17 int vis[1005][1005];
18 void bfs()
19 {
20 q.push(begin);
21 vis[x1][y1] = 0;
22 while(!q.empty())
23 {
24 State u = q.front();
25 q.pop();
26 if(u.x == x2 && u.y == y2 && u.count <= 2)
27 {
28 flag = 1;
29 return;
30 }
31 for(int i = 0; i < 4; i++)
32 {
33 State v;
34 v.x = u.x + dx[i];
35 v.y = u.y + dy[i];
36 v.count = u.count;
37 v.dir = i;
38 if(v.x>=0&&v.x<N&&v.y>=0&&v.y<M&&(map[v.x][v.y]==0||map[v.x][v.y]==map[x2][y2]))
39 {
40 if(v.dir != u.dir)
41 {
42 v.count = u.count + 1;
43 if(v.count > 2)
44 continue;
45 }
46 if(vis[v.x][v.y] >= v.count)
47 {
48 vis[v.x][v.y] = v.count;
49 q.push(v);
50 }
51 }
52 }
53 }
54 }
55 int main()
56 {
57 int ornum;
58 while(scanf("%d%d", &N, &M) && (N || M))
59 {
60 for(int i = 0; i < N; i++)
61 for(int j = 0; j < M; j++)
62 scanf("%d", &map[i][j]);
63 scanf("%d", &ornum);
64 while(ornum--)
65 {
66 scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
67 x1--; x2--; y1--; y2--;
68 flag = 0;
69 if((x1 != x2 || y1 != y2) && map[x1][y1] == map[x2][y2] && map[x1][y1] != 0)
70 {
71 for(int i = 0; i < N; i++)
72 for(int j = 0; j < M; j++)
73 vis[i][j] = 4;
74 begin.x = x1; begin.y = y1; begin.count = -1; begin.dir = -1;
75 bfs();
76 }
77 if(flag)
78 printf("YES\n");
79 else printf("NO\n");
80 while(!q.empty())
81 q.pop();
82 }
83 }
84 return 0;
85 }
浙公網安備 33010602011771號