偶数矩阵,神答案,我看不懂-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

偶数矩阵,神答案,我看不懂

a123456678 2016-06-06 13:55:33 1331

给定矩阵由0,1组成,使用最少的改变(使0变成1),使得任何元素的上下左右元素(如果存在)和为偶数

输入: 测试组数, 矩阵大小n ,矩阵每一个数

输出: 最小翻转次数,无法实现则输出-1
有谁能给我解释一下下面代码的check()函数和整段代码的思路,谢谢

 #include <algorithm>
    #include <iostream>
    #include <string>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    using namespace std;

    #define zero(a) memset(a,0,sizeof(a))
    #define one(a) memset(a,1,sizeof(a))
    #define fone(a) memset(a,-1,sizeof(a))
    #define pow2(a) ((a)*(a))
    #define pow3(a) ((pow2(a))*(a))
    #define MAX 10000000
    struct{
    int x,y;
    }a[20][20];
    int n;


    int check(int k)
    {
    int i;
    for(i=0;i<n;i++)
        a[0][i].y=0;
    i=0;
    while(k)
    {
        a[0][i].y=k%2;
        k=k/2;
        i++;
    }

    for(i=0;i<n;i++)
        if(a[0][i].x==1&&a[0][i].y==0)
            return -1;

    return 0;           
    }
    int fun()
    {
    int i,j;
    for(i=1;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            int sum=0;
            if(i>=2)
                sum+=a[i-2][j].y;
            if(j>0)
                sum+=a[i-1][j-1].y;
            if(j<n-1)
                sum+=a[i-1][j+1].y;
            if(sum%2==0)
                a[i][j].y=0;
            else
                a[i][j].y=1;
            if(a[i][j].y==0&&a[i][j].x==1)
                return MAX;
        }

    }

    int cnt=0;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(a[i][j].x==0&&a[i][j].y==1)
                cnt++;

    return cnt;
    }



    int main()
    {
        int T;
        int cas=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int i,j;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                scanf("%d",&a[i][j].x);
            }
        }

        int ans=MAX;

        for(i=0;i<(1<<n);i++)
        {
            if(check(i)==-1)
                continue;
            ans=min(ans,fun());
        }
        if(ans!=MAX)
            printf("Case %d: %d\n",cas++,ans);
        else
            printf("Case %d: -1\n",cas++);
    }
     return 0;
}
人工智能
分享到
取消 提交回答
全部回答(1)
  • a123456678
    2019-07-17 19:28:27

    枚举第一行,其它的你应该可以看的懂了

    0 0
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

推荐文章
相似问题
推荐课程