美文网首页
因数个数

因数个数

作者: _弓长_大人 | 来源:发表于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;
}

相关文章

  • 分解素因数——1. 质因数的个数

    质因数的个数 题目描述 求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=22235,共有...

  • 因数个数

  • 三升四数学(4)

    四,质数,合数 1.复习:因数的概念,找60的因数 2.正整数按因数的个数分类: ①一个因数 ②两个因数:质数(素...

  • 因数个数,所有因数的和

    今天讲一下求因数个数,求所有因数和的公式。若正整数N分解质因数的结果是 其中P1、P2、P3…Pn是不同的质数,则...

  • 质因数的个数

    题目链接题目描述求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=22235,共有5个质因...

  • 质数因数的个数

    求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。 解...

  • 6. 质因数的个数

    题目描述 求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=22235,共有5个质因数。 ...

  • 质因数分解

    题目:求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=22235,共有5个质因数。 x(...

  • 求最大公约数

    基本概念 因数 :若A=m×n,则称m,n是A的因数;A是m,n的倍数 一个数的最大因数和最小倍数都...

  • 小学数学基础知识

    质数与合数 合数指的是:一个数除了1和它本身以外还有别的因数(第三个因数),这个数叫做合数。 "0"“1”既不是质...

网友评论

      本文标题:因数个数

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