P1985 [USACO07OPEN]翻轉棋 題解

CSDN同步

原題連結

簡要題意：

給定一個 (01) 棋盤，每次可以翻轉一個“十”字形（即一個格子連同它四方向的相鄰格子，出界則不翻）。求在哪些格子上翻轉（十字形的中心）可以使得 翻轉後全 (0) 且 方案字典序最小 。

首先 (n,m leq 15)，本着面向資料範圍做題的原理，分析算法。

算法一

枚舉翻轉哪些格子進行驗證。

時間複雜度：(O(2^{n imes m} imes n imes m))，難以接受這樣的爆炸性複雜度。

算法二

需要我們分析一下題目。

我們肯定無法枚舉 (n) 行所有的翻轉情況，但我們可以枚舉 (1) 行。

• 什麼？枚舉 (1) 行？
• 沒錯，我們隻枚舉第 (1) 行是否翻轉。
• 那麼，其它行的怎麼辦呢？
• 其實很簡單。你想：在 按照行的順序枚舉 的情況下，如果 (a_{i-1,j} = 0)，那麼 (a_{i,j}) 肯定不翻；因為，其它能夠改變 (a_{i-1,j}) 的格子已經全部确定，再翻成 (1) 就翻不回去了。 那同理，如果 (a_{i-1,j}=1)，那麼 (a_{i,j}) 肯定翻，因為 其它能夠改變 (a_{i-1,j}) 的格子已經全部确定，不翻成 (0) 也就翻不回去了。

思路基本成型：枚舉第一行的翻轉狀态，以此遞推出每一個格子的翻轉狀态，模拟翻轉驗證，記錄字典序最小即可。

那麼，無解是什麼情況呢？

你會發現，如果最後無解的，那就肯定所有的 (1) 都在最後一行。

因為，前面的都已經被下面的格子重新翻回去了，而最後一行每人會翻它們。

這樣子枚舉即可。

時間複雜度：(O(2^m imes n imes m))，大概 (7.3 imes 10^6)，可以通過。

實際得分：(100pts).

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int N=20;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int h[N],a[N][N];
int n,m,b[N][N];
int turn[N][N],p[N][N];
int rev[N],ans=INT_MAX;

const int dx[5]={0,0,0,1,-1};
const int dy[5]={0,1,-1,0,0};

inline void _rev_(int x,int y) {
	for(int i=0;i<5;i++) {
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1 || ny<1 || nx>n || ny>m) continue;
		b[nx][ny]^=1;
	} //模拟翻轉過程
}

inline void check() {
	memset(turn,0,sizeof(turn));
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) b[i][j]=a[i][j]; //備份，準備翻轉
	for(int i=1;i<=m;i++)
		if(rev[i]) {
			_rev_(1,i); turn[1][i]=1;
		} //先翻第一行
	for(int i=2;i<=n;i++) for(int j=1;j<=m;j++)
		if(b[i-1][j]) turn[i][j]=1,_rev_(i,j); //依次确定後面的行
	for(int i=1;i<=m;i++) if(b[n][i]) return; //最後一行判斷
	int s=0;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++) if(turn[i][j]) s++; //記錄 1 的個數,便于字典序排序
	if(s<ans) { //較小
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) p[i][j]=turn[i][j];
		ans=s; //更新答案
	}
}

inline void dfs(int x) { //x 表示目前枚舉的是 1 行 x 列
	if(x>m) { //驗證
		check(); return;
	} for(int i=0;i<=1;i++)
		rev[x]=i,dfs(x+1); //是否翻轉目前格
}

int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read();
	dfs(1); //枚舉第一行狀态
	if(ans==INT_MAX) puts("IMPOSSIBLE"); //無解
	else 
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) printf("%d ",p[i][j]);
			puts("");
		} //輸出答案
	return 0;
}