``编程 OJ 4326 - 翻转棋 通过次数

7

提交次数

49

旧版界面 时间限制 : 1 秒 内存限制 : 128 MB FJ 知道，智商高的奶牛产奶量也大，所以他为奶牛们准备了一个翻动瓦片的益智游戏。

在一个 M × N M×N 的方阵上 （ 1 ≤ M , N ≤ 1 5 ） （1≤M,N≤15），每个格子都有一个可以翻转的瓦片。瓦片的一面是黑色，另一面是白色。对一个瓦片翻转，可以让它的颜色由黑到白，或是由白到黑。

然而奶牛们很笨拙，它们翻转一个格子的瓦片时，与其相邻的上下左右的所有瓦片也会翻转（如果有的话）。

现在奶牛们想知道，至少需要多少次翻转，使所有的瓦片都变成白色朝上呢？

输入 第一行两个整数M,N。接下来 M 行，每行 N 个整数，表示初始状态，0 表示白面朝上，1 表示黑面朝上。

输出 如果不能将所有瓦片都翻转为白面朝上的话，输出 ‘IMPOSSIBLE’。

否则输出 M 行，每行 N 个整数，第 i 行的第 j 个数代表第 i 行第 j 列的瓦片被翻转了多少次。

如果存在多种方案，输出字典序最小的方案。这里的字典序最小指将输出中的所有空白字符和换行去掉后，合并成的字符串字典序最小。

样例 输入复制 4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 输出复制 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 提示 （ 1 ≤ M , N ≤ 1 5 ） （1≤M,N≤15）

来源 USACO

C++ 1 ​ 2个月前 Accepted × 提交时间：2025-05-17 09:35:14

运行 ID: 284030

include

using namespace std; int b1[20], b2[20]; int main() {

int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
	for (int j = m - 1; j >= 0; j--) {
		int x;
		cin >> x;
		b1[i] |= (x << j);
	}
}
bool findans = false;
int p = (1 << m) - 1;
for (int i = 0; i < (1 << m); i++) {
	for (int j = 1; j <= n; j++) b2[j] = b1[j];
	b2[1] = b2[1] ^ (i << 1) ^ i ^ (i >> 1);
	b2[1] &= p;
	b2[2] = b2[2] ^ i;
	for (int j = 2; j <= n; j++) { //b2[j-1]就是第j行的操作方案
		b2[j] = b2[j] ^ (b2[j - 1] << 1) ^ b2[j - 1] ^ (b2[j - 1] >> 1);
		b2[j] &= p;
		b2[j + 1] = b2[j + 1] ^ b2[j - 1];
	}
	if (b2[n] == 0) {
		findans = true;
		for (int b = m - 1; b >= 0; b--) {
			cout << ((i >> b) & 1) << " ";
		}
		cout << endl;
		for (int a = 2; a <= n; a++) {
			for (int b = m - 1; b >=0; b--) {
				cout << ((b2[a - 1] >> b) & 1) << " ";
			}
			cout << endl;
		}
		break;
	}
}
if (!findans) cout << "IMPOSSIBLE";

}