《算法竞赛·快冲300题》每日一题：“二进制数独”

《算法竞赛·快冲300题》将于2024年出版，是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码，以中低档题为主，适合入门、进阶。

“ 二进制数独” ，链接： http://oj.ecustacm.cn/problem.php?id=1872

题目描述

【题目描述】 Farmer John的农民和他的奶牛们玩一个有趣的数独游戏。
和传统数独一样，这个游戏也是由一个9x9的方格组成，其中又被分为9个3x3的小方格。
不过不同的是，在这个游戏里，只使用二进制数字0和1来填充这些方格。
游戏的目标是尽可能少地改变其中的数字，以使得每行、每列和每个3x3的小方格里都包含偶数个数字1。
例如下面是一个合法的解：
000 000 000
001 000 100
001 000 100

000 110 000
000 110 000
000 000 000

000 000 000
000 000 000
000 000 000
对于给定的初始局面，你需要帮助这些奶牛计算出最小的修改次数。
【输入格式】 输入9行，每行9个字符。
每个字符为0或者1。
【输出格式】 输出一个整数表示答案
【输入样例】

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000
1
2
3
4
5
6
7
8
9

【输出样例】

3
1

---

题解

   概述题目：给出一个9×9的01矩阵，问最少修改几个数能使每行、每列以及每个九宫格中1的个数均为偶数。在样例中，一种修改方法是把上面两个1和右下角的1改为0，一共改3次。
   如何得到最小修改次数？先试试暴力搜索，用DFS编码，把所有可能的修改都尝试一遍。比较不同方法的修改次数，其中最少修改次数就是答案。有多少种可能的修改？有9×9=81个格子，每个格子有两种改法（改为0或1），共有$2^{81}$种修改方法。$2^{81}$显然太大了，不过加上剪枝之后，能优化很多。
   还有另外一种暴力法。共81个格子，最少修改次数是1，最多是81。从小到大逐一判断修改次数。先试只改一个格子，共81种修改方法，验证每种方法能不能达到目标；如果不行，再试改2个格子，共81×80种修改方法；等等。读者可以证明，这个暴力法和上面的暴力法的计算量差不多。可以用二分法优化，但只是把81优化到log81，其它的计算量仍然巨大。
   本题并不是求共有多少种修改方法，而是求最少修改次数。这种最优性问题，考虑用DP求解。
   下面模拟修改过程。设左上角坐标是(0,0)，右下角坐标是(8,8)。按从左到右，从上到下的顺序修改每个格子。从左上角(0,0)开始，先改第0行，再改第1行，一直到第8行。
   题目要求每行、每列、每3×3的方格都包含偶数个1，按这三个要求设计DP。DP的步骤是：
   （1）第0行，用DP记录第0行的9列格子的最少修改次数，需要验证第0行是否有偶数个1。
   （2）第1行，用DP记录第0~1行的9列格子的最少修改次数，需要验证第1行是否有偶数个1。
   （3）第2行，用DP记录记录第0~2行的9列格子的最少修改次数，需要验证第2行是否有偶数个1，并且验证三个3×3的九方格是否有偶数个1。
   等等，一直到第8行。
   每个小格子里面是0或者1，容易联想到用状态压缩DP。定义状态dp[][][][][]，dp[r][c][mask][sub][row]的含义是：
   （1）当前到达位置(r,c)，即第r行，第c列，代码中r和c的范围是0~8。
   （2）mask表示每列数字1出现的次数。设当前在第r行，统计0~r行的每一列的1的个数是否为偶数。为了简化用状态压缩，mask是一个9位的二进制数，每一位表示每一列的数字1出现的次数，奇数次为1，偶数次为0。例如000000001，表示最后一列（第8列）有奇数个1，其他列都是偶数个1。
   （3）sub表示每三列数字1出现的次数。同样用状态压缩，sub是一个3位的二进制数，3位分别表示第0_2列、第35列、第6~8列的数字1出现的次数，奇数次为1，偶数次为0。
   （4）row表示当前行数字1出现次数，奇数次为1，偶数次为0。
   DP用dfs()编程，从第0行第0列开始逐一处理第(r,c)位置的小格子，直到最后的第8行第8列。每个格子有两种改动方法，改为1或0。
   （1）改为1，修改次数ans：
      ans = !a[r][c] + dfs(r, c+1, mask ^ (1<    !a[r][c]：若原来a[r][c] = 0，现在改为a[r][c] = 1，修改次数ans+1；若原来a[r][c] = 1，现在仍有a[r][c] = 1，修改次数不变。两种情况下增加的修改次数都是!a[r][c]。
   c+1：继续dfs，往右走一列。
   mask ^ (1<    sub^(1<<(c/3))：更新每三列的奇偶，例如c = 2时，c/3 = 0，表示c在前三列中，更新前三列1的数量情况。
   !row：更新当前行中1的数量的奇偶，由于这一行多了一个1，新的row和原来相反。
   （2）改为0，修改次数ans：
      ans = min(ans, a[r][c] + dfs(r, c + 1, mask, sub, row));
   a[r][c]：若原来a[r][c] = 1，现在改为a[r][c] = 0，则修改次数ans+1；若原来a[r][c] = 0，修改次数不变。两种情况下增加的修改次数都是a[r][c]。
   c+1：继续dfs，往右走一列；
   mask、sub、row：因为(r,c)这个格子变成了0，没有增加1，所以都不变。
   其他处理见代码。
【重点】 状态压缩DP 。

C++代码

#include
using namespace std;
const int INF = 999;
bool a[9][9];         //存方格矩阵，行标0~8，列标0~8
int dp[9][9][1<<9][1<<3][2];  //dp[r][c][mask][sub][row]
int dfs(int r, int c, int mask, int sub, bool row){
    if(r == 9)        //0-8行已经填满，必须保证mask=0，sub=0，row=0
        return (!mask && !sub && !row) ? 0 : INF;
    if(c == 9){       //0-8列已经填完
        if(row)  return INF;                //1、保证本行偶数个
        if(r%3 == 2 && sub)  return INF;    //2、保证每三行统计一下每三列数字1出现次数为偶数个
        return dfs(r + 1, 0, mask, sub, 0); //3、下一行
    }
    int& ans = dp[r][c][mask][sub][row];    //ans是dp的别名，把下面的ans改成dp，结果一样
    if(ans != -1) return ans;  //记忆化
    ans = !a[r][c] + dfs(r, c+1, mask ^ (1<<c), sub^(1<<(c/3)), !row);
        //a[r][c]设置为1。  若原来a[r][c]=0，ans+1
    ans = min(ans, a[r][c] + dfs(r, c + 1, mask, sub, row));
        //a[r][c]设置为0。  若原来a[r][c]=1，ans+1
    return ans;
}
int main(){
    for(int i = 0; i < 9; i++){
        string s;  cin >> s;
        for(int j = 0; j < 9; j++)
            a[i][j] = (s[j] == '1'); //存到 a[0][0]~a[8][8]
    }
    memset(dp, -1, sizeof(dp));
    cout<<dfs(0, 0, 0, 0, 0)<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Java代码

import java.util.*;
import java.io.*;
public class Main {
    private static final int INF = 999;
    private static boolean[][] a; // 存方格矩阵，行标0~8，列标0~8
    private static int[][][][][] dp; // dp[r][c][mask][sub][row]
    private static int dfs(int r, int c, int mask, int sub, int row) {
        if (r == 9)  // 0-8行已经填满，必须保证mask=0，sub=0，row=0
            return (mask == 0 && sub == 0 && row == 0) ? 0 : INF;        
        if (c == 9) { // 0-8列已经填完
            if (row==1)  return INF;   // 1、保证本行偶数个
            if (r % 3 == 2 && sub != 0)    return INF; 
// 2、保证每三行统计一下每三列数字1出现次数为偶数个
            return dfs(r + 1, 0, mask, sub, 0); // 3、下一行
        }
        if (dp[r][c][mask][sub][row] != -1)    // 记忆化
            return dp[r][c][mask][sub][row];
        int ans;
        ans = (!a[r][c]?1:0) + dfs(r, c+1, mask ^ (1<<c), sub^(1<<(c/3)), 1 - row);
        ans = Math.min(ans, (a[r][c]?1:0) + dfs(r, c + 1, mask, sub, row));
        dp[r][c][mask][sub][row] = ans;
        return ans;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        a = new boolean[9][9];
        for (int i = 0; i < 9; i++) {
            String s = scanner.next();
            for (int j = 0; j < 9; j++) 
                a[i][j] = (s.charAt(j) == '1'); // 存到 a[0][0]~a[8][8]            
        }
        dp = new int[9][9][1 << 9][1 << 3][2];
        for (int[][][][] rows : dp) 
            for (int[][][] row : rows) 
                for (int[][] sub : row) 
                    for (int[] arr : sub) 
                        Arrays.fill(arr, -1);
        System.out.println(dfs(0, 0, 0, 0, 0));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

Python代码

INF = 999
a = [[False for j in range(9)] for i in range(9)] # 存方格矩阵，行标0~8，列标0~8
dp = [[[[[-1 for k in range(2)] for j in range(1 << 3)] for i in range(1 << 9)] for c in range(9)] for r in range(9)]
def dfs(r, c, mask, sub, row):
    if r == 9: # 0-8行已经填满，必须保证mask=0，sub=0，row=0
        return 0 if not mask and not sub and not row else INF
    if c == 9: # 0-8列已经填完
        if row:   return INF       # 1、保证本行偶数个
        if r % 3 == 2 and sub: 
            return INF             # 2、保证每三行统计一下每三列数字1出现次数为偶数个
        return dfs(r + 1, 0, mask, sub, False)     # 3、下一行
    if dp[r][c][mask][sub][row] != -1:
        return dp[r][c][mask][sub][row] # 记忆化
ans = dfs(r, c+1, mask ^ (1 << c), sub ^ (1 << (c // 3)), not row) + (not a[r][c]) 
# a[r][c]设置为1。若原来a[r][c]=0，ans+1
ans = min(ans, dfs(r, c+1, mask, sub, row) + a[r][c])
  # a[r][c]设置为0。若原来a[r][c]=1，ans+1
    dp[r][c][mask][sub][row] = ans        # 存储结果
    return ans
for i in range(9):
    s = input().strip()
    for j in range(9):   a[i][j] = s[j] == '1' # 存到 a[0][0]~a[8][8]
print(dfs(0, 0, 0, 0, False))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24