百度之星

01 题 简单dfs

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=105;
bool vis[N][N];
char s[N][N];
int n,m;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
inline bool inbond(int x,int y)
{
    return x>=0&&x<n&&y>=0&&y<m;
}
void dfs(int x,int y,char c,int &num)
{
    vis[x][y]=1,num++;
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(inbond(xx,yy)&&!vis[xx][yy]&&s[xx][yy]==c)
            dfs(xx,yy,c,num);
    }
}
inline Find(int &x,int &y,char c)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(!vis[i][j]&&s[i][j]==c)
            {
                x=i,y=j;
                break;
            }
        }
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
            scanf("%s",s[i]);
        int num0=0,num1=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(s[i][j]=='0')
                    num0++;
                else
                    num1++;
            }
        }
        if(num0==0)
        {
            puts("1");
            continue;
        }
        if(num1==0)
        {
            puts("-1");
            continue;
        }
        int x0=-1,y0=-1,x1=-1,y1=-1;
        Find(x1,y1,'1');
        if(x1==-1)
        {
            puts("-1");
            continue;
        }
        int tmp1=0;
        dfs(x1,y1,'1',tmp1);
        memset(vis,0,sizeof(vis));
        if(tmp1!=num1)
        {
            puts("-1");
            continue;
        }
        int tmp0=0;
        for(int i=0;i<m;i++)
        {
            if(s[0][i]=='0'&&!vis[0][i])
                dfs(0,i,'0',tmp0);
            if(s[n-1][i]=='0'&&!vis[n-1][i])
                dfs(n-1,i,'0',tmp0);
        }
        for(int i=0;i<n;i++)
        {
            if(s[i][0]=='0'&&!vis[i][0])
                dfs(i,0,'0',tmp0);
            if(s[i][m-1]=='0'&&!vis[i][m-1])
                dfs(i,m-1,'0',tmp0);
        }
        if(tmp0)
        {
            if(tmp0==num0)
            {
                puts("1");
                continue;
            }
            int temp=0;
            int x00=-1,y00=-1;
            Find(x00,y00,'0');
            dfs(x00,y00,'0',temp);
            if(temp+tmp0==num0)
                puts("0");
            else
                puts("-1");
        }
        else
        {
            int x00=-1,y00=-1;
            Find(x00,y00,'0');
            int tmp00=0;
            dfs(x00,y00,'0',tmp00);
            if(tmp00==num0)
                puts("0");
            else
                puts("-1");
        }
    }
    return 0;
}