51nod1416(dfs)

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1416

题意：中文题诶～

思路：dfs

搜索同一颜色的点。。

只要不往返回方向走，遇到以标记的点即出现了环。。。

代码：

 1 #include <iostream>
 2 #define MAXN 60
 3 using namespace std;
 4 
 5 char mp[MAXN][MAXN];
 6 int vis[MAXN][MAXN], n, m;
 7 int dis[4][2]={0, 1, 1, 0, -1, 0, 0, -1};
 8 bool flag=false;
 9 char ch;
10 
11 void dfs(int x, int y, int cnt){
12     if(x<0||x>=n||y<0||y>=m||mp[x][y]!=ch||flag) return;
13     if(vis[x][y]){
14         flag=true;
15         return;
16     }
17     vis[x][y]=1;
18     for(int i=0; i<4; i++){
19         if(i+cnt==3) continue;
20         int fx=x+dis[i][0];
21         int fy=y+dis[i][1];
22         dfs(fx, fy, i);
23     }
24 }
25 
26 int main(void){
27     cin >> n >> m;
28     for(int i=0; i<n; i++){
29         for(int j=0; j<m; j++){
30             cin >> mp[i][j];
31         }
32     }
33     for(int i=0; i<n; i++){
34         for(int j=0; j<m; j++){
35             if(flag){
36                 cout << "Yes" << endl;
37                 return 0;
38             }
39             if(!vis[i][j]){
40                 ch=mp[i][j];
41                 dfs(i, j, -1);
42             }
43         }
44     }
45     cout << "No" << endl;
46     return 0;
47 }

View Code