2010-1078
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
by xvls
首先要理解此题的枚举方法。
先看第一种pattern的情况。
[[BR]]
.*.[[BR]]
* *[[BR]]
.*.[[BR]]
注意到对任何一个位置，点i次和点i+2次，是没有任何差别的，因此我们只要考虑点与不点这两种情况。
因为最后我们希望得到的是全盘为白棋，而点第i行的棋子，只会影响第i-1行和第i行和第i+1行的，因此我们可以枚举第1行我们点哪些棋子的情况，比如点了第一行的第k1, k2, k3, ..., ki(i <= m)个，那么在没有点第二行的时候，第一行的黑白格局就完全确定了。我们的目标是通过第二行的点击把第一行完全变白，注意到点击第二行的某个棋子，第一行只有一个棋子会受到影响，如果第一行的第a1, a2, a3, ..., ai(i <= m)个棋子为黑色的话，那么我们就只能点第二行的第a1, a2, a3, ..., ai个，也就是说，第一行点好后，第二行的选择就是完全确定了的，以此类推，第3, 4, ..., n行的选择也是完全确定的。在n行的选择都确定后，我们就要判断第n行是否全为白色，如果是，就得到一个可行的方案，否则就是不可行的。枚举所有第一行的选择，找出所有可行方案中需要点击最少的次数，就是我们需要的结果。
对于第二个pattern，它和第一个pattern的情况有所不同，因为第i行的点击会改变第i-1行中的两个，所以不能按照上述的方法搞。但是此时我们只要把整个图逆时针旋转90度，就会发现问题又变成了和第一个pattern相似的问题，这样第二行的点击就只改变第一行的一个元素了。[[BR]]
**. [[BR]]
* * -> [[BR]]
*.. [[BR]]
[[BR]]
.*.[[BR]]
* .[[BR]]
***[[BR]]
现在来考虑时间复杂度。枚举第一行需要2^m^，对每种枚举的情况算出第二行点击带来的对第二和第三行的影响，需要O(m)，因此计算整个棋盘就要O(n*m)，还有4种pattern和150个cases，最高的复杂度约为2^15^*15*15*4*150＝？没算，总之就是复杂度太高了。那怎么办呢？且听下回分解。
好，我们接着上次讲的，怎么办呢？注意到每行每个棋子的状态只有黑和白两种状态，如果把黑的换成1，白的换成0，会怎么样呢，那一行就变成一个二进制的数啦！哈哈哈，太神奇了！那么怎么用这个数的运算来表示点棋子的操作呢?我们知道点一下会改变一个棋子的状态，就是0变1，1变0，嗯，好熟悉，这不就是与1的异或运算吗？下面我们来模拟一下这个过程。就比如pattern1吧：
{{{
100101
001001
110010
}}}
此时要对第二行操作，也就是说要把第一行的1全变成0，那么第二行必须点第1，4，6个，变成：
{{{
000000
010001
010111
}}}
用x[1..3]表示第1到3行，其实这个操作就是:
{{{
#!cpp
x[2] ^= (x[1]>>1) ^ ((x[1]<<1) & mask); //mask = 111111 = (1<<6) - 1
x[3] ^= x[1];
}}}
于是我们就可以对第一种pattern写一个函数，返回需要点的棋子个数：
{{{
#!cpp
int gao1(int x[], int n) {
int ret = 0;
for (int i = 0; i < n; i++) {
if ( (ret += ones[x[i]]) > minstep)
return ret;
x[i+1] ^= ((x[i]<<1) ^ (x[i]>>1) ^ x[i]) & mask;
x[i+2] ^= x[i];
}
if (x[n] == 0)
return ret;
else
return Inf;
}
}}}
函数中的ones[i]就是指i这个数的二进制编码中有多少个1，也就是我们要点多少次。minstep是一个全局变量，记录了前面已经算过的最少次数，如果在某一步中发现了要返回的次数已经比minstep大了，就可以立即跳出，省时间嘛！我们要枚举的就是x[0]，从0 ~ 2^m^-1，就相当于枚举了第一行的所有点击情况。于是在main()里面可以这样写：
{{{
#!cpp
mask = (1 << m) - 1;
for (int i = 0; i <= mask; i++) {
c[0] = i;
copy(a, a + n, c + 1);
int tmp = gao1(c, n);
if(tmp < minstep || (tmp == minstep && idx > 1)) {
minstep = tmp;
idx = 1;
}
}
}}}
整个程序如下，参考了诗歌的代码，a[i]记录了第i行表示的二进制数，b[j]记录了第j行表示的二进制数：
{{{
#!cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int Inf = 10000;
int mask, minstep, idx;
int ones[1<<20];
int gao1(int x[], int n) {
int ret = 0;
for (int i = 0; i < n; i++) {
if ( (ret += ones[x[i]]) > minstep)
return ret;
x[i+1] ^= ((x[i]<<1) ^ (x[i]>>1) ^ x[i]) & mask;
x[i+2] ^= x[i];
}
if (x[n] == 0)
return ret;
else
return Inf;
}
int gao2(int x[], int n) {
int ret = 0;
for (int i = 0; i < n; i++) {
if ((ret += ones[x[i]]) > minstep)
return ret;
x[i+1] ^= (x[i]>>1) ^ x[i];
x[i+2] ^= ((x[i]>>1) ^ (x[i]<<1) ^ x[i]) & mask;
}
return (x[n] == 0) ? ret : Inf;
}
int gao3(int x[], int n) {
int ret = 0;
for (int i = 0; i < n; i++) {
if ((ret += ones[x[i]]) > minstep)
return ret;
x[i+1] ^= ((x[i]>>1) ^ (x[i]<<1) ^ x[i]) & mask;
x[i+2] ^= (x[i]>>1) ^ x[i];
}
return (x[n] == 0) ? ret : Inf;
}
int gao4(int x[], int n) {
int ret = 0;
for (int i = 0; i < n; i++) {
if ((ret += ones[x[i]]) > minstep)
return ret;
x[i+1] ^= ((x[i]>>1) ^ (x[i]<<1) ^ x[i]) & mask;
x[i+2] ^= (x[i]>>1) ^ (x[i]<<1) & mask;
}
return (x[n] == 0) ? ret : Inf;
}
void init() {
ones[0] = 0;
for (int i = 1; i < (1 << 20); i++)
ones[i] = ones[i>>1] + (i & 1);
}
int main() {
int a[20], b[20], c[20];
char buff[20];
int n, m;
init();
while (scanf("%d %d", &n, &m) && n) {
fill(a, a + n, 0);
fill(b, b + m, 0);
for (int i = 0; i < n; i++) {
scanf(" %s", buff);
for (int j = 0 ; j < m ; j++) {
if (buff[j] == '1') {
a[i] |= (1 << (m - j - 1));
b[j] |= (1 << i);
}
}
}
idx = 5;
minstep = n * m + 1;
//gao1
mask = (1 << m) - 1;
for (int i = 0; i <= mask; i++) {
c[0] = i;
copy(a, a + n, c + 1);
int tmp = gao1(c, n);
if(tmp < minstep || (tmp == minstep && idx > 1)) {
minstep = tmp;
idx = 1;
}
}
//gao3
mask = (1 << n) - 1;
for (int i = 0; i <= mask; i++) {
c[0] = i;
copy(b, b + m, c + 1);
int tmp = gao3(c, m);
if(tmp < minstep || (tmp == minstep && idx > 3)) {
minstep = tmp;
idx = 3;
}
}
//gao4
for (int i = 0; i <= mask; i++) {
c[0] = i;
copy(b, b + m, c + 1);
int tmp = gao4(c, m);
if(tmp < minstep || (tmp == minstep && idx > 4)) {
minstep = tmp;
idx = 4;
}
}
//gao2
reverse(b, b + m);
for (int i = 0; i <= mask; i++) {
c[0] = i;
copy(b, b + m, c + 1);
int tmp = gao2(c, m);
if(tmp < minstep || (tmp == minstep && idx > 2)) {
minstep = tmp;
idx = 2;
}
}
if( minstep < n * m + 1)
printf("%d %d\n", idx, minstep);
else
puts("Impossible");
}
return 0;
}
}}}by xvls
首先要理解此题的枚举方法。
先看第一种pattern的情况。
.*.
- *
.*.
注意到对任何一个位置，点i次和点i+2次，是没有任何差别的，因此我们只要考虑点与不点这两种情况。
因为最后我们希望得到的是全盘为白棋，而点第i行的棋子，只会影响第i-1行和第i行和第i+1行的，因此我们可以枚举第1行我们点哪些棋子的情况，比如点了第一行的第k1, k2, k3, ..., ki(i <= m)个，那么在没有点第二行的时候，第一行的黑白格局就完全确定了。我们的目标是通过第二行的点击把第一行完全变白，注意到点击第二行的某个棋子，第一行只有一个棋子会受到影响，如果第一行的第a1, a2, a3, ..., ai(i <= m)个棋子为黑色的话，那么我们就只能点第二行的第a1, a2, a3, ..., ai个，也就是说，第一行点好后，第二行的选择就是完全确定了的，以此类推，第3, 4, ..., n行的选择也是完全确定的。在n行的选择都确定后，我们就要判断第n行是否全为白色，如果是，就得到一个可行的方案，否则就是不可行的。枚举所有第一行的选择，找出所有可行方案中需要点击最少的次数，就是我们需要的结果。
对于第二个pattern，它和第一个pattern的情况有所不同，因为第i行的点击会改变第i-1行中的两个，所以不能按照上述的方法搞。但是此时我们只要把整个图逆时针旋转90度，就会发现问题又变成了和第一个pattern相似的问题，这样第二行的点击就只改变第一行的一个元素了。
**.
- * ->
*..
.*.
- .
***
现在来考虑时间复杂度。枚举第一行需要2m，对每种枚举的情况算出第二行点击带来的对第二和第三行的影响，需要O(m)，因此计算整个棋盘就要O(n*m)，还有4种pattern和150个cases，最高的复杂度约为215*15*15*4*150＝？没算，总之就是复杂度太高了。那怎么办呢？且听下回分解。
好，我们接着上次讲的，怎么办呢？注意到每行每个棋子的状态只有黑和白两种状态，如果把黑的换成1，白的换成0，会怎么样呢，那一行就变成一个二进制的数啦！哈哈哈，太神奇了！那么怎么用这个数的运算来表示点棋子的操作呢?我们知道点一下会改变一个棋子的状态，就是0变1，1变0，嗯，好熟悉，这不就是与1的异或运算吗？下面我们来模拟一下这个过程。就比如pattern1吧：
100101
001001
110010
此时要对第二行操作，也就是说要把第一行的1全变成0，那么第二行必须点第1，4，6个，变成：
000000
010001
010111
用x[1..3]表示第1到3行，其实这个操作就是:
x[2] ^= (x[1]>>1) ^ ((x[1]<<1) & mask); //mask = 111111 = (1<<6) - 1
x[3] ^= x[1];
于是我们就可以对第一种pattern写一个函数，返回需要点的棋子个数：
int gao1(int x[], int n) {
int ret = 0;
for (int i = 0; i < n; i++) {
if ( (ret += ones[x[i]]) > minstep)
return ret;
x[i+1] ^= ((x[i]<<1) ^ (x[i]>>1) ^ x[i]) & mask;
x[i+2] ^= x[i];
}
if (x[n] == 0)
return ret;
else
return Inf;
}
函数中的ones[i]就是指i这个数的二进制编码中有多少个1，也就是我们要点多少次。minstep是一个全局变量，记录了前面已经算过的最少次数，如果在某一步中发现了要返回的次数已经比minstep大了，就可以立即跳出，省时间嘛！我们要枚举的就是x[0]，从0 ~ 2m-1，就相当于枚举了第一行的所有点击情况。于是在main()里面可以这样写：
mask = (1 << m) - 1;
for (int i = 0; i <= mask; i++) {
c[0] = i;
copy(a, a + n, c + 1);
int tmp = gao1(c, n);
if(tmp < minstep || (tmp == minstep && idx > 1)) {
minstep = tmp;
idx = 1;
}
}
整个程序如下，参考了诗歌的代码，a[i]记录了第i行表示的二进制数，b[j]记录了第j行表示的二进制数：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int Inf = 10000;
int mask, minstep, idx;
int ones[1<<20];
int gao1(int x[], int n) {
int ret = 0;
for (int i = 0; i < n; i++) {
if ( (ret += ones[x[i]]) > minstep)
return ret;
x[i+1] ^= ((x[i]<<1) ^ (x[i]>>1) ^ x[i]) & mask;
x[i+2] ^= x[i];
}
if (x[n] == 0)
return ret;
else
return Inf;
}
int gao2(int x[], int n) {
int ret = 0;
for (int i = 0; i < n; i++) {
if ((ret += ones[x[i]]) > minstep)
return ret;
x[i+1] ^= (x[i]>>1) ^ x[i];
x[i+2] ^= ((x[i]>>1) ^ (x[i]<<1) ^ x[i]) & mask;
}
return (x[n] == 0) ? ret : Inf;
}
int gao3(int x[], int n) {
int ret = 0;
for (int i = 0; i < n; i++) {
if ((ret += ones[x[i]]) > minstep)
return ret;
x[i+1] ^= ((x[i]>>1) ^ (x[i]<<1) ^ x[i]) & mask;
x[i+2] ^= (x[i]>>1) ^ x[i];
}
return (x[n] == 0) ? ret : Inf;
}
int gao4(int x[], int n) {
int ret = 0;
for (int i = 0; i < n; i++) {
if ((ret += ones[x[i]]) > minstep)
return ret;
x[i+1] ^= ((x[i]>>1) ^ (x[i]<<1) ^ x[i]) & mask;
x[i+2] ^= (x[i]>>1) ^ (x[i]<<1) & mask;
}
return (x[n] == 0) ? ret : Inf;
}
void init() {
ones[0] = 0;
for (int i = 1; i < (1 << 20); i++)
ones[i] = ones[i>>1] + (i & 1);
}
int main() {
int a[20], b[20], c[20];
char buff[20];
int n, m;
init();
while (scanf("%d %d", &n, &m) && n) {
fill(a, a + n, 0);
fill(b, b + m, 0);
for (int i = 0; i < n; i++) {
scanf(" %s", buff);
for (int j = 0 ; j < m ; j++) {
if (buff[j] == '1') {
a[i] |= (1 << (m - j - 1));
b[j] |= (1 << i);
}
}
}
idx = 5;
minstep = n * m + 1;
//gao1
mask = (1 << m) - 1;
for (int i = 0; i <= mask; i++) {
c[0] = i;
copy(a, a + n, c + 1);
int tmp = gao1(c, n);
if(tmp < minstep || (tmp == minstep && idx > 1)) {
minstep = tmp;
idx = 1;
}
}
//gao3
mask = (1 << n) - 1;
for (int i = 0; i <= mask; i++) {
c[0] = i;
copy(b, b + m, c + 1);
int tmp = gao3(c, m);
if(tmp < minstep || (tmp == minstep && idx > 3)) {
minstep = tmp;
idx = 3;
}
}
//gao4
for (int i = 0; i <= mask; i++) {
c[0] = i;
copy(b, b + m, c + 1);
int tmp = gao4(c, m);
if(tmp < minstep || (tmp == minstep && idx > 4)) {
minstep = tmp;
idx = 4;
}
}
//gao2
reverse(b, b + m);
for (int i = 0; i <= mask; i++) {
c[0] = i;
copy(b, b + m, c + 1);
int tmp = gao2(c, m);
if(tmp < minstep || (tmp == minstep && idx > 2)) {
minstep = tmp;
idx = 2;
}
}
if( minstep < n * m + 1)
printf("%d %d\n", idx, minstep);
else
puts("Impossible");
}
return 0;
}