开发者社区> 问答> 正文

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

给定矩阵由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;
}

展开
收起
a123456678 2016-06-06 13:55:33 2123 0
1 条回答
写回答
取消 提交回答
  • 枚举第一行,其它的你应该可以看的懂了

    2019-07-17 19:28:27
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
图解算法小抄 立即下载
考察数据科学家支持向量机(SVM)知识的25道题,快来测测吧 立即下载
低代码开发师(初级)实战教程 立即下载