美文网首页
因数个数

因数个数

作者: _弓长_大人 | 来源:发表于2018-09-25 12:47 被阅读4次
    #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;
    }
    

    相关文章

      网友评论

          本文标题:因数个数

          本文链接:https://www.haomeiwen.com/subject/bdoyrxtx.html