题解：P3032 [USACO11NOV] Binary Sudoku G

· · 题解

一看就是道动规，但是我们可以尝试用贪心和模拟来解决这道题，于是便有了这篇题解。

我们考虑计算每一个点更改后的价值，如果该点所在的行、列和九宫格都存在奇数个 1，那么更改这个点就会产生 3 的价值；如果该点所在的行、列和九宫格中只有两者存在奇数个 1，那么更改它会解决两个问题，但又会产生一个新的问题，故价值为 1。值得注意的是此处更改完一个有两个问题的点后会导致一些点的问题数增加，可能会产生有三个问题的点，所以一直更改有两个问题的点是不优的。

很容易发现我们应该先算清楚总共有多少问题并对每一个点计算它所在位置的问题数，优先更改有三个问题的点（因为其产生的价值大）。如果目前有三个问题的点更新完了，便去更新 1 个有两个问题的点，再去检查一遍是否又有有三个问题的点出现。如此往复直至没有有两个或者三个问题的点。这时我们只会有一些互不相干的有一个问题的点，剩下的更改次数就是最后还剩下的问题数。

虽然说得不难，但实现起来还是有很多细节的，可以用来锻炼各位的代码能力。

奉上调了两个周的代码：

#include<bits/stdc++.h>
using namespace std;
char a[15][15];
int vis[15][15],idx[15][15][5],shu[15][15],now,ans;
int fx[10]={0,1,1,1,4,4,4,7,7,7},fy[10]={0,1,4,7,1,4,7,1,4,7};
signed main(){
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=9;i++){//行
        int sum=0;
        for(int j=1;j<=9;j++){
            sum+=a[i][j]-'0';
        }
        if(sum%2==1){
            now++;
            for(int j=1;j<=9;j++){
                vis[i][j]++;
                idx[i][j][1]=1;
            }
        }
    }
    for(int i=1;i<=9;i++){//列
        int sum=0;
        for(int j=1;j<=9;j++){
            sum+=a[j][i]-'0';
        }
        if(sum%2==1){
            now++;
            for(int j=1;j<=9;j++){
                vis[j][i]++;
                idx[j][i][2]=1;
            }
        }
    }
    for(int k=1;k<=9;k++){//九宫格
        int x=fx[k],y=fy[k],sum=0;
        for(int i=x;i<=x+2;i++){
            for(int j=y;j<=y+2;j++){
                sum+=a[i][j]-'0';
                shu[i][j]=k;
            }
        }
        if(sum%2==1){
            now++;
            for(int i=x;i<=x+2;i++){
                for(int j=y;j<=y+2;j++){
                    vis[i][j]++,idx[i][j][3]=1;
                }
            }
        }
    }
    //now：目前的总问题数
    bool flag=0;
    while(now>0){
        flag=0;
        int start=now;
        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                if(vis[i][j]==3){//有三个问题的
                    now-=3,ans++;
                    for(int k=1;k<=9;k++){
                        vis[i][k]--,idx[i][k][1]=0;
                    }
                    for(int k=1;k<=9;k++){
                        vis[k][j]--,idx[k][j][2]=0;
                    }
                    int s=shu[i][j],x=fx[s],y=fy[s];
                    for(int x1=x;x1<=x+2;x1++){
                        for(int y1=y;y1<=y+2;y1++){
                            vis[x1][y1]--,idx[x1][y1][3]=0;
                        }
                    }
                }
            }
        }
        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                if(vis[i][j]==2){//有两个问题的
                    now--,ans++;
                    int op=6;
                    if(idx[i][j][1]==1){
                        op-=1;
                        for(int k=1;k<=9;k++){
                            vis[i][k]--,idx[i][k][1]=0;
                        }
                    }
                    if(idx[i][j][2]==1){
                        op-=2;
                        for(int k=1;k<=9;k++){
                            vis[k][j]--,idx[k][j][2]=0;
                        }
                    }
                    if(idx[i][j][3]==1){
                        op-=3;
                        int s=shu[i][j],x=fx[s],y=fy[s];
                        for(int x1=x;x1<=x+2;x1++){
                            for(int y1=y;y1<=y+2;y1++){
                                vis[x1][y1]--,idx[x1][y1][3]=0;
                            }
                        }
                    }
                    if(op==1){
                        for(int k=1;k<=9;k++){
                            vis[i][k]++,idx[i][k][1]=1;
                        }
                    }
                    if(op==2){
                        for(int k=1;k<=9;k++){
                            vis[k][j]++,idx[k][j][2]=1;
                        }
                    }
                    if(op==3){
                        int x=i,y=j;
                        for(int x1=x;x1<=x+2;x1++){
                            for(int y1=y;y1<=y+2;y1++){
                                vis[x1][y1]++,idx[x1][y1][3]=1;
                            }
                        }
                    }
                    flag=1;
                    break;//只操作一个数
                }
            }
            if(flag) break;
        }
        if(start==now) break;//没有有三个或者两个问题的点
    }
    cout<<ans+now;
    return 0;
}

代码实测比其他算法都要快很多。（可以用来抢最优解）