本文主要是介绍深度优先搜索练习之神奇的矩环（dfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
深度优先搜索练习之神奇的矩环
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic Discuss
Problem Description
小鑫的女朋友被魔王抢走了！
魔王留给小鑫一张n*m大的表，上面有各种各样的颜色，用A-Z这26个字母来表示。魔王留给他一个任务，如果小鑫可以在这张表中找出任意一个长度大于1的环，并且这个环的颜色是相同的，魔王就把小鑫的女朋友还给他。为了从魔王手中夺回他的女朋友，小鑫请你帮忙，你能帮帮他吗？
Input
多组输入。
每组的第一行有两个整数n,m。代表表的大小。
接下来是由A-Z的一些字母所构成的n行m列的表。
1<=n,m<=200
Output
如果可以救回他的女朋友，输出Yes，否则输出No
Sample Input
4 7 ABCBBAA BCBCBCB AABBCCA ACCCBBB 10 3 AAC ABB BBA AAC CBC CCA CBB CCA CCB BAA
Sample Output
No Yes
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=210;
struct node
{char x;int ans;node():ans(0){};
};
int vis[maxn][maxn];
char mp[maxn][maxn];int n,m;
int flag;int mx[]={0,1,0,-1};
int my[]={1,0,-1,0};int judge(int x, int y)
{if(x>=0&&x<n && y>=0&&y<m)return 1;return 0;
}
void dfs(int x, int y,int lx, int ly)
{if(flag){return;}vis[x][y] = 1;for(int i = 0; i < 4; i++){int dx = x + mx[i];int dy = y + my[i];if(judge(dx,dy)&&vis[dx][dy] && mp[x][y] == mp[dx][dy]&& dx!=lx && dy!=ly){flag=1;return;}if(judge(dx, dy) && !vis[dx][dy] && mp[x][y] == mp[dx][dy]){dfs(dx,dy,x,y);}}vis[x][y] = 0;
}
int main()
{while(~scanf("%d%d", &n, &m)){for(int i = 0; i < n; i++)scanf("%s", mp[i]);memset(vis, 0, sizeof(vis));flag = 0;for(int i = 0; i < n; i++){for(int j = 0; j< m; j++){dfs(i,j,0,0);}}if(flag)printf("Yes\n");elseprintf("No\n");}return 0;
}
这篇关于深度优先搜索练习之神奇的矩环（dfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
