POJ 3279 FLiptile

本文最后更新于:2020年6月10日 下午

【POJ】 3279 Fliptile

题目链接:poj-3279

Description

Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M × N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.

As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.

Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word “IMPOSSIBLE”.


Input

Line 1: Two space-separated integers: M and N
Lines 2.. M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white


Output

Lines 1.. M: Each line contains N space-separated integers, each specifying how many times to flip that particular location.


Sample Input

4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

Sample Output

0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0

题目理解

​ 给定一个M * N的棋盘,上面有M * N个棋子,每个棋子有上下两面,一面为黑色,另一面为白色,用1表示黑色,用0表示黑色,现在FJ的牛用蹄子去翻动棋子,目的是将所有的棋子都翻转为白色,但是牛的蹄子比较大,每次反转中心的一个棋子都会同时反转周围的四个棋子。

​ 如果可以将所有棋子都翻转为白色,则输出每个棋子的翻转情况,1代表该棋子要翻转,0代表该棋子不需要翻转,特别的,如果有多个答案,则输出翻转次数最小且字符排序最小的答案。如果不存在全部反转为白色的可能,则输出IMPOSSIBLE

​ 每一个棋子翻转两次就复原了,所以每个棋子只有翻和不翻两种可能,在棋盘较小的情况下可以直接暴力枚举,本题1 <= M, N <= 15显然会TLE。

​ 这里我们不妨枚举第一行的所有情况,有2 ^ N种情况,不管第一行是否全为白色,不是白色的我们交给第二行来翻转,这样我们就可以根据第一行的情况来确定第二行的情况,然后根据第二行的情况来确定第三行的情况……最后确定到最后一行,当最后一行确定后,我们查看最后一行的颜色情况,如果最后一行中含有黑色,则继续枚举过程,如果最后一行全为白色,则找到答案。

​ 由于每一个棋子只有翻与不翻两种情况,故可以使用二进制来表示,使用二进制来枚举第一行的所有情况,既可以表示翻转情况,又兼顾了字符序,二进制从小到大枚举,先被找到答案字符序小于后被找到的答案。


代码

#include<iostream>
#include<cstring>
using namespace std;

int m, n, step, tmp;
int mp[20][20], vis[20][20], ans[20][20];
int dy[] = {1, -1, 0, 0};	//用来遍历正在判定的棋子四周棋子的情况 
int dx[] = {0, 0, -1, 0};

bool isBlack(int x, int y){		//判断遍历到的棋子当前的颜色 
	int t = mp[x][y];	//t为单数则是黑色,反之为白色,因为翻转两次就还原 
	for(int i = 0; i < 4; ++i){		//遍历该棋子四周棋子是否翻转过 
		if(vis[x + dx[i]][y + dy[i]] == 1)
			++t;
	}
	return t & 1;
}

void DFS(int t){
	for(int i = m - 1; i >= 0; --i){	//该循环遍历自一行的所有情况,使用到位运算 
		if(t & 1){
			vis[0][i] = 1;
			++step;
		}
		t >>= 1;
	}
	
	for(int i = 1; i < m; ++i)		//该循环遍历第二行到最后一行,确定除第一行外的每一个棋子的翻转情况 
		for(int j = 0; j < n; ++j){
			if(isBlack(i - 1, j)){	//如果相邻的上一行的棋子是黑色,则该棋子需要翻转 
				vis[i][j] = 1;
				++step;
			}
		}
		
	for(int i = 0; i < n; ++i)	//遍历最后一行是否全为白色 
		if(isBlack(m - 1, i))	//如果出现黑色则返回,进行下一种情况的搜索 
			return;
			
	if(step < tmp){		//更新记录翻转次数最小的情况 
		tmp = step;
		memcpy(ans, vis, sizeof(vis));
	}
	return;
}

int main(){
	while(cin >> m >> n){
		tmp = 32769;
		memset(ans, 0, sizeof(vis));
		for(int i = 0; i < m; ++i)
			for(int j = 0; j < n; ++j)
				cin >> mp[i][j];
		for(int i = 0; i < (1 << n); ++i){	//遍历第一行的2 ^ n种情况 
			memset(vis, 0, sizeof(vis));
			step = 0;
			DFS(i);
		}
		if(tmp != 32769) 	//32768 = 2 ^ 15, 总翻转次数必然小于该数值,以此来判断是否有可能 
			for(int i = 0; i < m; ++i)
				for(int j = 0; j < n; ++j)
					cout << ans[i][j] << (j == n - 1 ? '\n' : ' ');
		else
			cout << "IMPOSSIBLE" << endl;
	}
	
	return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!