17-比赛2 F - Fox And Two Dots (dfs)

=================================================================================================================================
题意:是能否找到一连串同样的字母至少四个形成循环(贯通)
通过dfs 按照相同的字母遍历一遍, 且阻止其走回头路,那么深搜之后再次搜到被标记的点,则肯定就形成了循环。
详情解释,见代码。
=================================================================================================================================
 代码:
 #include<bits/stdc++.h>
using namespace std;
int n,m;
char Map[][];
bool book[][];
bool flag;
void dfs(int y,int x,int rey,int rex)
{
for(int i =;i<=;i++)
{
int ty=y,tx=x;
if(i==) ty++; //四个方向
if(i==) ty--;
if(i==) tx++;
if(i==) tx--;
if(ty<||ty>n||tx<||tx>m) continue;
if(ty==rey&&tx==rex) continue; //阻止往回走
if(Map[y][x]==Map[ty][tx]) //确保是相同的字母
{
if(book[ty][tx]==) {flag = ;break;}
book[ty][tx]=;
dfs(ty,tx,y,x);
}
}
return;
}
int main()
{
scanf("%d %d",&n,&m);
for(int y = ;y<=n;++y)
for(int x=;x<=m;++x)
{
cin>>Map[y][x];
} for(int y = ;y<=n;++y)
{
for(int x=;x<=m;++x)
{
if(book[y][x]==) continue;
book[y][x]=; //走过的点都标记上
dfs(y,x,,);
if(flag==) break;
}
if(flag==) break;
}
printf(flag==?"Yes\n":"No\n");
}
17-比赛2  F - Fox And Two Dots (dfs)17-比赛2  F - Fox And Two Dots (dfs)17-比赛2  F - Fox And Two Dots (dfs)17-比赛2  F - Fox And Two Dots (dfs)17-比赛2  F - Fox And Two Dots (dfs)17-比赛2  F - Fox And Two Dots (dfs)
上一篇:svn使用(服务器端和客户端)


下一篇:车牌识别--S5PV210測试