think: 1感覺自己用的不是深度優先搜索啊，——話落即發現如何判錯自己的代碼，人果然還是否定自己比較容易..無語啊
sdut原題鏈接
深度優先搜索練習之神奇的矩環 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 小鑫的女朋友被魔王搶走了！ 魔王留給小鑫一張n*m大的表，上面有各種各樣的顏色，用A-Z這26個字母來表示。魔王留給他一個任務，如果小鑫可以在這張表中找出任意一個長度大于1的環，并且這個環的顏色是相同的，魔王就把小鑫的女朋友還給他。為了從魔王手中奪回他的女朋友，小鑫請你幫忙，你能幫幫他嗎？
Input 多組輸入。 每組的第一行有兩個整數n,m。代表表的大小。 接下來是由A-Z的一些字母所構成的n行m列的表。 1<=n,m<=200
Output 如果可以救回他的女朋友，輸出Yes，否則輸出No
Example Input 4 7 ABCBBAA BCBCBCB AABBCCA ACCCBBB 10 3 AAC ABB BBA AAC CBC CCA CBB CCA CCB BAA
Example Output No Yes
Hint
Author
以下為accpted代碼——感覺后臺數據和自己挺親的 數據 5 5 AAAAA ABBBA AAAAA CCCCC AAAAA 即可判錯以下代碼
#include <stdio.h>#include <string.h>int main(){ int n, m, i, j; char s[204][204]; while(scanf("%d %d", &n, &m) != EOF) { int flag = 0; for(i = 0; i < n; i++) { scanf("%s", s[i]); } for(i = 0; i < n-1; i++) { for(j = 0; j < m-1; j++) { if(s[i][j] == s[i][j+1]) { if(s[i][j] == s[i+1][j]) { if(s[i][j] == s[i+1][j+1]) { flag = 1; break; } } } } if(j != m-1) break; } if(flag) printf("Yes/n"); else printf("No/n"); } return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 120KBSubmit time: 2017-02-16 20:53:44****************************************************/以下為accepted建議參考代碼
#include <stdio.h>#include <string.h>char map[200][200];int v[200][200], flag;void dfs(int x, int y, int x1, int y1, int n, int m){ v[x][y] = 1; if(flag == 1) { return; } if(y-1 >= 0 && map[x][y] == map[x][y-1]) { if(v[x][y-1] == 1 && (x != x1 || y-1 != y1)) { flag = 1; } else if(v[x][y-1] == 0) { dfs(x, y-1, x, y, n, m); } } if(x-1 >= 0 && map[x][y] == map[x-1][y]) { if(v[x-1][y] == 1 && (x-1 != x1 || y != y1)) { flag = 1; } else if(v[x-1][y] == 0) { dfs(x-1, y, x, y, n, m); } } if(y+1 < m && map[x][y] == map[x][y+1]) { if(v[x][y+1] == 1 && (x != x1 || y+1 != y1)) { flag = 1; } else if(v[x][y+1] == 0) { dfs(x, y+1, x, y, n, m); } } if(x+1 < n && map[x][y] == map[x+1][y]) { if(v[x+1][y] == 1 && (x+1 != x1 || y != y1)) { flag = 1; } else if(v[x+1][y] == 0) { dfs(x+1, y, x, y, n, m); } }}int main(){ int n, m, i, j; while(scanf("%d %d", &n, &m) != EOF) { flag = 0; memset(v, 0, sizeof(v)); for(i = 0; i < n; i++) { scanf("%s", map[i]); } for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { if(v[i][j] == 0) { dfs(i, j, i, j, n, m); } if(flag == 1) { break; } } if(j != m) { break; } } if(flag) printf("Yes/n"); else printf("No/n"); } return 0;}/***************************************************User name: Result: AcceptedTake time: 4msTake Memory: 280KBSubmit time: 2017-02-16 21:40:33****************************************************/新聞熱點
疑難解答
