简单环路
题目描述
有一个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：重新构图——把每个字母当成一个点，判断上下左右如果有相同的则连上一条边。用tarjan算法来进行判环，若遇见连接到更小的搜索序号dfn[]时,则可以认为这时找到了一个环，然后把这个环弹出来，数数长度（看是否满足要求），再逆序放回去。
方法2：据说搜索就可以了，只有相同字符之间的才可以进行搜索；后台数据比较弱，我用错误的代码都过了。
答案：
#include <stdio.h> #include <stdlib.h> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #include<math.h> #include <string.h> #include<set> using namespace std; #define inf 0x3f3f3f3f #define maxn 10000000 const double pi=acos(-1.0); #define ll long long #define N 55 #define M 50*50+5 char a[55][55]; vector<int>G[M];//表示每个点的周围四个点的情况 int low_link[M],dfn[M],inst[M]; int Time; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0} }; int n,m; bool flag; stack<int>st; void judge(int i,int j,int num){ for(int k=0;k<=3;k++){ int dx=i+dir[k][0]; int dy=j+dir[k][1]; if(dx>=0&&dx<=n-1&&dy>=0&&dy<=m-1&&a[dx][dy]==a[i][j]){ G[num].push_back(dx*m+dy); } } } void init(){ Time=0; flag=false; for(int i=0;i<=n*m;i++) G[i].clear(); memset(low_link,0,sizeof(low_link)); memset(dfn,0,sizeof(dfn)); memset(inst,0,sizeof(inst)); while(!st.empty()) st.pop(); } void tarjan(int u,int fa){ low_link[u]=dfn[u]=++Time; st.push(u); inst[u]=1; for(int i=0;i<(int)G[u].size();i++){ int v=G[u][i]; if(!dfn[v]){ tarjan(v,u); low_link[u]=min(low_link[u],low_link[v]); } else if(inst[v]==1&&v!=fa){ low_link[u]=min(low_link[u],dfn[v]); stack<int>q; int cnt=1; while(st.top()!=v){ q.push(st.top()); st.pop(); cnt++; } if(cnt>=4){ flag=true; // printf("u=%d v=%d ",u,v); } while(q.size()>0){ st.push(q.top());q.pop(); } } } if(low_link[u]==dfn[u]){ while(st.top()!=u){ // printf("u=%d %d ",u,st.top()); inst[st.top()]=0;st.pop(); } inst[st.top()]=0;st.pop(); } } void debug(){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int num=i*m+j; for(int v=0;v<G[num].size();v++){ printf("%d:%d ",num,G[num][v]); } cout<<endl; } } } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ init(); for(int i=0;i<n;i++) scanf("%s",a[i]); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int num=i*m+j; judge(i,j,num); } } // debug(); for(int i=0;!flag&&i<n;i++){ for(int j=0;!flag&&j<m;j++){ int num=i*m+j; if(!dfn[num]){ tarjan(num,-1); //if(flag==true) // printf("Yes num=%d ",num); } } } if(flag==true) printf("Yes "); else printf("No "); } return 0; }