网站集约化建设优势,腾讯微信朋友圈广告代理,关键词云图,塑料机械怎么做网站《算法竞赛快冲300题》将于2024年出版#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码#xff0c;以中低档题为主#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
二…《算法竞赛·快冲300题》将于2024年出版是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码以中低档题为主适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
二进制数独” 链接
http://oj.ecustacm.cn/problem.php?id1872 题目描述
【题目描述】 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【输出样例】
3题解 概述题目给出一个9×9的01矩阵问最少修改几个数能使每行、每列以及每个九宫格中1的个数均为偶数。在样例中一种修改方法是把上面两个1和右下角的1改为0一共改3次。 如何得到最小修改次数先试试暴力搜索用DFS编码把所有可能的修改都尝试一遍。比较不同方法的修改次数其中最少修改次数就是答案。有多少种可能的修改有9×981个格子每个格子有两种改法改为0或1共有 2 81 2^{81} 281种修改方法。 2 81 2^{81} 281显然太大了不过加上剪枝之后能优化很多。 还有另外一种暴力法。共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。 2mask表示每列数字1出现的次数。设当前在第r行统计0~r行的每一列的1的个数是否为偶数。为了简化用状态压缩mask是一个9位的二进制数每一位表示每一列的数字1出现的次数奇数次为1偶数次为0。例如000000001表示最后一列第8列有奇数个1其他列都是偶数个1。 3sub表示每三列数字1出现的次数。同样用状态压缩sub是一个3位的二进制数3位分别表示第02列、第35列、第6~8列的数字1出现的次数奇数次为1偶数次为0。 4row表示当前行数字1出现次数奇数次为1偶数次为0。 DP用dfs()编程从第0行第0列开始逐一处理第(r,c)位置的小格子直到最后的第8行第8列。每个格子有两种改动方法改为1或0。 1改为1修改次数ans ans !a[r][c] dfs(r, c1, mask ^ (1c), sub^(1(c/3)), !row); !a[r][c]若原来a[r][c] 0现在改为a[r][c] 1修改次数ans1若原来a[r][c] 1现在仍有a[r][c] 1修改次数不变。两种情况下增加的修改次数都是!a[r][c]。 c1继续dfs往右走一列。 mask ^ (1c)第c列多了一个1更新第c列的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则修改次数ans1若原来a[r][c] 0修改次数不变。两种情况下增加的修改次数都是a[r][c]。 c1继续dfs往右走一列 mask、sub、row因为(r,c)这个格子变成了0没有增加1所以都不变。 其他处理见代码。 【重点】 状态压缩DP 。
C代码
#includebits/stdc.h
using namespace std;
const int INF 999;
bool a[9][9]; //存方格矩阵行标0~8列标0~8
int dp[9][9][19][13][2]; //dp[r][c][mask][sub][row]
int dfs(int r, int c, int mask, int sub, bool row){if(r 9) //0-8行已经填满必须保证mask0sub0row0return (!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, c1, mask ^ (1c), sub^(1(c/3)), !row);//a[r][c]设置为1。 若原来a[r][c]0ans1ans min(ans, a[r][c] dfs(r, c 1, mask, sub, row));//a[r][c]设置为0。 若原来a[r][c]1ans1return 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));coutdfs(0, 0, 0, 0, 0)endl;
}Java代码
import java.util.*;
import java.io.*;
public class Main {private static final int INF 999;private static boolean[][] a; // 存方格矩阵行标0~8列标0~8private 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行已经填满必须保证mask0sub0row0return (mask 0 sub 0 row 0) ? 0 : INF; if (c 9) { // 0-8列已经填完if (row1) 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, c1, mask ^ (1c), 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));}
}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行已经填满必须保证mask0sub0row0return 0 if not mask and not sub and not row else INFif 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, c1, mask ^ (1 c), sub ^ (1 (c // 3)), not row) (not a[r][c])
# a[r][c]设置为1。若原来a[r][c]0ans1
ans min(ans, dfs(r, c1, mask, sub, row) a[r][c])# a[r][c]设置为0。若原来a[r][c]1ans1dp[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))
