深度优先搜索练习之神奇的矩环

2019-11-08 18:25:40

字体：大中小

来源：转载

供稿：网友

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****************************************************/

上一篇：编写项目规范

下一篇：线段树，不要依赖模板