题目描述
农夫约翰的奶牛喜欢玩“数独”这个流行游戏的有趣变体。
它们的数独在 $9$ 个 $3 \times 3$ 的子网格构成的 $9 \times 9$ 网格内进行,这一点和常规数独一样。
但是奶牛们的版本是只用二进制数字:
000 000 000
001 000 100
000 000 000
000 110 000
000 111 000
000 000 000
000 000 000
000 000 000
000 000 000
二进制数独的目标是尽可能少的切换其中的一些数字(0
变为 1
,1
变为 0
),以使每行,每列以及每个 $3 \times 3$ 子网格内均包含偶数个 1
。
对于上面的示例,一种只切换 3
个数字的解决方案如下:
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$ 位二进制字符串,用来描述数独矩阵。
输出格式
输出解决该问题所需要的最少切换数字数量。
输入样例:
000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000
输出样例:
3
算法
(bfs)
考虑到每个点有两种状态,一共有 $2^{81}$ 中状态,肯定不能用普通的广搜。
(实际上我是试了一遍才知道的,实践出真知)
那写宽搜就至少是要写个 A*
。
考虑如何计算估价函数:假设有 a
行的 1
的个数为奇数,b
列 1
的个数为奇数,c
个 $3 \times 3$ 的格子内的 1
的数量为奇数。
假设情况最优,那么每次操作一个格子会同时将 a
、b
、c
都减 1
,那么至少就要操作 $max({a, b, c})$ 次。
所以可以让估价函数 $f() = max(a, b, c)$
然后就不难写出 A*
的代码了。
$C ++ $ 代码
#include <queue>
#include <map>
using namespace std;
int ones[512]; // 预处理 0 ~ 1 << 9 中每个数字的 1 的个数
inline int max(int a, int b) // 返回 a 和 b 中的较大值
{
return a > b ? a : b;
}
struct point // 存每个状态
{
int s[9]; // S 存该状态,每行用一个二进制数存储
bool operator < (const point &t) const // 要用到 stl 的 map,需要先重载小于号
{
for (int i = 0; i < 9; i ++ )
if (s[i] != t.s[i])
return s[i] < t.s[i];
return false;
}
inline void read() // 读入该状态
{
for (int i = 0; i < 9; i ++ , getchar())
for (int j = 0; j < 9; j ++ )
s[i] |= (getchar() != 48) << j;
}
inline void print() // 输出该状态,用于 debug
{
for (int i = 0; i < 9; i ++ , putchar(10))
for (int j = 8; ~j; j -- )
putchar((s[i] >> j & 1) ^ 48);
}
inline int f() // 计算 a, b, c
{
int a = 0, b = 0, c = 0;
for (int i = 0, cnt; i < 9; i ++ )
{
if (ones[s[i]] & 1) a ++ ; // 如果说 s[i] 中的 1 的个数为奇数,那么 a ++ ;
cnt = 0;
for (int j = 0; j < 9; j ++ ) // 计算第 i 列的 1 的个数
if (s[j] >> i & 1)
cnt ++ ;
if (cnt & 1) b ++ ; // 如果第 i 列的 1 的个数为奇数,那么 b ++ ;
cnt = 0;
for (int x = i / 3 * 3; x / 3 == i / 3; x ++ ) // 计算第 (i / 3, i % 3) 个 3 * 3 方格中的 1 的个数
for (int y = i % 3 * 3; y / 3 == i % 3; y ++ )
if (s[x] >> y & 1) cnt ++ ;
if (cnt & 1) c ++ ; // 如果为奇数,那么 c ++ ;
}
return max(max(a, b), c); // 返回 a, b, c 中的最大值
}
} g;
map<point, int> dist;
typedef pair<int, point> ppi;
priority_queue<ppi, vector<ppi>, greater<ppi>> heap;
inline void init() // 初始化 ones 数组
{
for (int i = 1; i < 512; i ++ )
for (int j = i; j; j &= j - 1)
ones[i] ++ ;
}
inline int bfs() // 广搜
{
dist[g] = 0;
heap.push(make_pair(g.f(), g));
while (heap.size())
{
point t = heap.top().second, state;
heap.pop();
if (!t.f()) return dist[t]; // 如果 t.a, t.b, t.c 都为 0,那么返回说明到达了一种合法状态,返回到该状态的距离。
for (int i = 0; i < 9; i ++ )
for (int j = 0; j < 9; j ++ )
{
state = t;
state.s[i] ^= 1 << j;
if (!dist.count(state))
{
dist[state] = dist[t] + 1;
heap.push(make_pair(dist[state] + state.f(), state));
}
}
}
return 0;
}
int main()
{
init(); g.read(); // 初始化 ones 数组,读入 g
printf("%d\n", bfs());
return 0;
}
然后你会发现,你写了半天的代码,只过了11个点。。T了最后一个点。。
考虑优化。
我第一个想到的,是减少计算 a
、b
、c
的计算量。
对于每个状态,不再记录整个状态,而是分别用三个变量记录:行上1
的状态、列上 1
的状态、$3 \times 3$ 方格内 1
的状态。
在改变每个点上的数时,不用再算一遍 a
、b
、c
,而是直接改原来的 a
、b
、c
。
$C ++ $ 代码
这里偷个懒,只注释和上面不同的地方
#include <queue>
#include <map>
using namespace std;
inline int max(int a, int b)
{
return a > b ? a : b;
}
struct point
{
int a, b, c;
int row, col, cell; // 分别存 行上 1 的状态,列上 1 的状态,3 * 3 方格内 1 的状态
bool operator < (const point &t) const
{
if (t.row != row) return row < t.row;
if (t.col != col) return col < t.col;
if (t.cell != cell) return cell < t.cell;
return false;
}
inline void init() // 读入该状态,并初始化 a, b, c, row, col, cell
{
row = col = cell = a = b = c = 0;
for (int i = 0; i < 9; i ++ , getchar())
for (int j = 0; j < 9; j ++ )
if (getchar() != 48)
{
row ^= 1 << i, col ^= 1 << j;
cell ^= 1 << i / 3 * 3 + j / 3;
}
for (int i = 0; i < 9; i ++ )
{
if (row >> i & 1) a ++ ;
if (col >> i & 1) b ++ ;
if (cell >> i & 1) c ++ ;
}
}
inline void draw(int x, int y)
{
row ^= 1 << x, col ^= 1 << y;
cell ^= 1 << x / 3 * 3 + y / 3;
a += ((row >> x & 1) << 1) - 1;
b += ((col >> y & 1) << 1) - 1;
c += ((cell >> x / 3 * 3 + y / 3 & 1) << 1) - 1;
}
inline int f()
{
return max(max(a, b), c);
}
} g;
map<point, int> dist;
typedef pair<int, point> ppi;
priority_queue<ppi, vector<ppi>, greater<ppi>> heap;
inline int bfs()
{
dist[g] = 0;
heap.push(make_pair(g.f(), g));
while (heap.size())
{
point t = heap.top().second, state;
heap.pop();
if (!t.f()) return dist[t];
for (int i = 0; i < 9; i ++ )
for (int j = 0; j < 9; j ++ )
{
state = t; state.draw(i, j);
if (!dist.count(state))
{
dist[state] = dist[t] + 1;
heap.push(make_pair(dist[state] + state.f(), state));
}
}
}
return 0;
}
int main()
{
g.init();
printf("%d\n", bfs());
return 0;
}
emmm交上去一看。。原来T的那个点还是T的。。
于是我放弃了 A*
,开始思考其它方法
正解
(暴力枚举,深度优先搜索,迭代加深,IDA*) $O(2 ^ n)$
代码全删,将搜索方式改为IDA*,详见代码注释。
如果上面的都能看懂,那看下面的也不算难。
时间复杂度
巨玄学。。
看似是 $\mathcal O(2 ^ n)$。。
但是由于各种神奇剪枝优化,不仅能过,还跑的贼快。。
$C ++ $ 代码
#include <stdio.h>
int max_depth;
int a, b, c;
int row, col, cell;
int f() // 估价函数
{
return a > b ? a > c ? a : c : b > c ? b : c;
}
void draw(int x, int y) // 改变点 (x, y) 的状态
{
row ^= 1 << x, col ^= 1 << y;
cell ^= 1 << x / 3 * 3 + y / 3;
a += ((row >> x & 1) << 1) - 1;
b += ((col >> y & 1) << 1) - 1;
c += ((cell >> x / 3 * 3 + y / 3 & 1) << 1) - 1;
}
bool dfs(int x, int y, int depth) // 当前遍历到的点坐标为 (x, y),当前所改变点的状态的数量为 de[th。
{
if(depth > max_depth) return false; // 如果当前深度超过最大深度,那么返回 false
if (x == 8 && y == 8) // 如果跑到最后一个点了,那么 check 一遍该状态是否合法
{
for (int i = 0; i < 9; i ++ ) // 从 0 ~ 8 枚举所有 行、列、3 * 3 方格
if((row >> i & 1) | (row >> i & 1) | (cell >> i & 1)) // 如果当前有一行、列、3 * 3 方格中的 1 的个数为奇数
return false; // 那么就返回 false
return true; // 否则返回 true
}
if((row >> x & 1) | (col >> y & 1) | (cell >> x / 3 * 3 + y / 3 & 1)) // 如果当前位置所在的 行、列、3 * 3 方格内的 1 的个数为奇数
{
draw(x, y); // 那么先爆搜一下改变当前位置点的状态的情况
if (depth + 1 + f() <= max_depth) // 如果 当前深度 + 估价深度 + 1 在 max_depth 以内
if (y != 8 ? dfs(x, y + 1, depth + 1) : dfs(x + 1, 0, depth + 1)) // 那么爆搜该点下一个节点
return true; // 如果下一个点搜成功了,那么返回 true
draw(x, y); // 搜失败了,改回来
}
if (y != 8 ? dfs(x, y + 1, depth) : dfs(x + 1, 0, depth)) // 爆搜不改当前位置点的状态的情况
return true; // 搜成功了,返回 true
return false; // 都搜失败了(好惨。。),返回 false
}
int main()
{
for (int i = 0; i < 9; i ++ , getchar())
for (int j = 0; j < 9; j ++ )
if (getchar() != 48)
draw(i, j);
while (!dfs(0, 0, 0)) max_depth ++ ; // 如果搜的不成功,就一直往后搜
printf("%d\n", max_depth);
return 0;
}
Orztql
果然这种题只有抽神和yxc以及墨染空和wzc和cht和彩色铅笔和……才能做出来……%%%
抽风老师好优秀
%%%