首页 > 代码库 > Codeforces Round #290 (Div. 2) B. Fox And Two Dots(DFS)

Codeforces Round #290 (Div. 2) B. Fox And Two Dots(DFS)

http://codeforces.com/problemset/problem/510/B

#include "cstdio"
#include "cstring"
int r,c;
char map[55][55];
int vis[55][55];
int mark;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int judge(int x,int y)
{
    if(x<0||x>=r||y<0||y>=c)
        return 0;
    return 1;
}
void dfs(int x,int y,int perX,int perY)
{
    if(!judge(x,y))
        return;
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(map[xx][yy]==map[x][y]&&judge(xx,yy)&&(xx!=perX||yy!=perY))
        {
            if(vis[xx][yy])
            {
                mark=1;
                return;
            }
            dfs(xx,yy,x,y);
        }
    }
    return;
}
int main()
{
    while(scanf("%d%d",&r,&c)!=EOF)
    {
        memset(vis,0,sizeof(vis));
        for(int i=0;i<r;i++)
            scanf("%s",map[i]);
        mark=0;
        int flag=1;
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(!vis[i][j])
                {
                    dfs(i,j,0,0);
                   if(mark)
                    {
                        break;
                    }
                }
            }
           if(mark)
            {
                break;
            }
        }
        if(mark)
            printf("Yes\n");
        else
            printf("No\n");

    }
    return 0;
}

 

Codeforces Round #290 (Div. 2) B. Fox And Two Dots(DFS)