17-比赛2 F

Fox And Two Dots

=================================================================================================================================

题意：是能否找到一连串同样的字母至少四个形成循环（贯通）

通过dfs 按照相同的字母遍历一遍，且阻止其走回头路，那么深搜之后再次搜到被标记的点，则肯定就形成了循环。

详情解释，见代码。

=================================================================================================================================

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 char Map[100][100];
 5 bool book[100][100];
 6 bool flag;
 7 void dfs(int y,int x,int rey,int rex)
 8 {
 9     for(int i =1;i<=4;i++)
10     {
11         int ty=y,tx=x;
12         if(i==1) ty++;   //四个方向
13         if(i==2) ty--;
14         if(i==3) tx++;
15         if(i==4) tx--;
16         if(ty<1||ty>n||tx<1||tx>m) continue;
17         if(ty==rey&&tx==rex) continue; //阻止往回走
18         if(Map[y][x]==Map[ty][tx])     //确保是相同的字母
19         {
20             if(book[ty][tx]==1) {flag = 1;break;}
21             book[ty][tx]=1; 
22             dfs(ty,tx,y,x);
23         }
24     }
25     return;
26 }
27 int main()
28 {
29         scanf("%d %d",&n,&m);
30         for(int y = 1;y<=n;++y)
31             for(int x=1;x<=m;++x)
32         {
33             cin>>Map[y][x];
34         }
35 
36         for(int y = 1;y<=n;++y)
37         {
38             for(int x=1;x<=m;++x)
39             {
40                 if(book[y][x]==1) continue;
41                 book[y][x]=1;   //走过的点都标记上
42                 dfs(y,x,0,0);
43                 if(flag==1) break;
44             }
45             if(flag==1) break;
46         }
47         printf(flag==1?"Yes
":"No
");
48 }