【简易DFS/BFS+标记搜索次序的数组】zznu-2025 : 简单环路

2025 : 简单环路

时间限制:1 Sec 内存限制:128 MiB
提交:145 答案正确:41

提交状态编辑讨论区

题目描述

有一个N x M 大小的地图，地图中的每个单元包含一个大写字母。

若两个相邻的(这里的相邻指“上下左右”相邻)点上的字母相同，我们可以用线段连接这两个点。

若存在一个包含同一字母的环路，那么连接这些点我们可以得到一个多边形，

当且仅当多边形的边数大于等于4时，我们称这幅地图中存在“简单环路”。

现在给你一份地图，你来判断是否存在“简单环路”。

列如：

3 4

AAAA

ABCA

AAAA

字符“A”可以构成一个“简单环路”，其边数为4。

输入

第一行输入两个正整数n,m，2<=n,m<=50，分别表示地图的行列数。

接下来输入n行，每行m个大写字母。

输出

若存在“简单环路”输出“Yes”，否则输出“No”。

样例输入

复制

3 4
AAAA
ABCA
AADA

样例输出

复制

No

大致思路：

　　1、深度搜索这个图，不需要回头即可，一直沿着上下左右可以走的方向走下去，用order来标记一下搜索的先后次序，每次搜索一个节点更新dp里的值为order的值，并把当前节点置为‘#’，所有判断回路的时候判断 abs(dp[x][y]-dp[xx][yy])>=3，即可。

　　2.我的另一篇博客里，用的是tarjan算法判环的。本篇的搜索，用广搜也是同一个道理。时间复杂度O(n*m)。

　　3.提供几个参考数据：

3 4
AAAA
ABCA
AAAA
3 4
AAAA
ABCA
AADA
3 4
AABB
ABBB
AAAA
3 4
AABB
BBBA
AAAA

简单题解：

　　解封此debug();函数的注释，可以看到搜索内容。其余有注释。

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <stack>
 7 #include <vector>
 8 #include<math.h>
 9 #include <string.h>
10 #include<deque>
11 using namespace std;
12 #define inf 0x3f3f3f3f
13 const double pi=acos(-1.0);
14 #define ll long long
15 using namespace std;
16 #define inf 0x3f3f3f3f
17 #define N 55
18 
19 char str[N][N];
20 int flag,n,m;
21 int b[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
22 int dp[N][N];//存贮每个点遍历时的次序
23 
24 void dfs(int x,int y,int sum,char ch,int order){
25     if(flag==1)
26         return ;
27     dp[x][y]=order;
28     str[x][y]='#';
29 
30     for(int i=0; i<4; i++){
31         int xx=x+b[i][0];
32         int yy=y+b[i][1];
33         if(xx>=n||yy>=m||xx<0||yy<0)//单向深度搜索，只搜索相同的字符
34             continue;
35         if(str[xx][yy]=='#'&&dp[xx][yy]!=-1){//遇见本次搜索中相同的字符
36             if(abs(dp[x][y]-dp[xx][yy])>=3){//之前搜索过的字符，判断两者之间的次序差即可
37                 flag=1;
38                 return ;
39             }
40         }
41         if(str[xx][yy]!=ch)//可能遇见dp[xx][yy]==-1的情况，需要过滤掉
42             continue;
43         dfs(xx,yy,sum,ch,order+1);
44     }
45 }
46 void debug(){
47     for(int i=1;i<=n;i++){
48         for(int j=1;j<=m;j++){
49             printf("*%d ",dp[i-1][j-1]);
50         }
51         cout<<endl;
52     }
53     printf("flag=%d
",flag);
54 }
55 int main()
56 {
57     while(cin>>n>>m){
58         flag=0;
59         for(int i=0; i<n; i++)
60             scanf("%s",str[i]);
61         for(int i=0; i<n; i++){
62             for(int j=0; j<m; j++){
63                  if(flag==1)
64                     break;
65                 if(str[i][j]!='#'){
66                     memset(dp,-1,sizeof(dp));
67                      dfs(i,j,0,str[i][j],0);
68                     // debug();//解封此注释，可以看到搜索内容
69                 }
70             }
71         }
72 
73         if(flag)
74             printf("Yes
");
75         else
76             printf("No
");
77 
78     }
79     return 0;
80 }

View Code