游客 注册 | 登录
中文 | En

3320 - 翻转棋

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

农夫约翰知道，聪明的奶牛可以产更多的牛奶。他为奶牛设计了一种智力游戏，名叫翻转棋。翻转棋可以分成M × N (1 ≤ M, N ≤ 15)个格子，每个格子有两种颜色，一面是黑的，一面是白的。
    一旦翻转某个格子，这个格子的颜色就会颠倒。如果把所有的格子都翻成白的，就算奶牛赢了。然而，奶牛的蹄子很大，一旦它们打算翻转某个格子，这个格子附近（即和这个格子有公共边）的格子也会被翻转。一直翻来翻去也很无聊，奶牛们想最小化必须翻动的次数。
    请帮助奶牛确定翻动的最少次数和具体的翻法。如果最小解有多个，则输出在字典序意义下最小的那个，如果不可能完成任务，则只要输出一行单词：IMPOSSIBLE。

题目输入

第一行：两个用空格分开的整数：M和N
第二行到M + 1行：第i + 1行从左至右依次描述了棋盘第i行的的颜色，共记N个用空格分开的整数，1 代表黑色，0 代表白色。

题目输出

第一行到第M行：每行输出N个用空格分开的整数，表示在这个格子上翻转的次数。

输入/输出样例

输入格式

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

C++解答

/*
	Name: fliptile
	Author: 靳帅祥
	Date: 22/10/14 08:58
	Description:
*/
#include <cstdio>
#include <climits>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
using namespace std;

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

int H=0,L=0;

bool jsx=false;

class node{
	public:
		int Step;
		int G[20][20];
		bool operator < (const node& b) const {
			if(Step==b.Step){
				for(int i=1;i<=H;++i){
					for(int j=1;j<=L;++j){
						if(G[i][j] < b.G[i][j]) return true;
						else return false;
					}
				}
				return true;
			}
			return Step < b.Step;
		}		
}E,Map,Ans;

inline bool PD(int x,int y){
	if(x>0 && y>0 && x<=H && y<=L) return true;
	return false;
}

inline bool Full(node b){
	for(int i=1;i<=H;++i){
		for(int j=1;j<=L;++j){
			if(b.G[i][j]!=0) return false; 
		}
	}
	return true;
}

inline void Turn(int x,int y){
	Map.G[x][y]++;	Map.Step++;
	E.G[x][y]=!E.G[x][y];
	for(int i=0;i<4;++i){
		int xx=x+dx[i],yy=y+dy[i];
		if(PD(xx,yy))	E.G[xx][yy]=!E.G[xx][yy];
	}
}

inline void DEAL(){
	node temp1=E;
	node temp2=Map;//储存状态 
	for(int i=2;i<=H;++i){
		for(int j=1;j<=L;++j){
			if(E.G[i-1][j]==1)	Turn(i,j);
		}
	}
	if(Full(E)){
		if(!jsx){	Ans=Map; jsx=true; }
		else{
			if(Map < Ans){  Ans=Map; }
		}
	}
	E=temp1;	Map=temp2;//还原 
}

void DFS(int pos,int F){
	if(pos==L+1){ DEAL(); return; }
	
	if(F==0){	DFS(pos+1,0);	DFS(pos+1,1);	}
	else{
		node t1=E,t2=Map;
		Turn(1,pos);	DFS(pos+1,0);	DFS(pos+1,1);
		E=t1; Map=t2;//还原 
	}
}

int main(){
	//freopen("fliptile.in","r",stdin);
	//freopen("fliptile.out","w",stdout);
	
	scanf("%d%d",&H,&L);
	for(int i=1;i<=H;++i){
		for(int j=1;j<=L;++j){
			scanf("%d",&E.G[i][j]);
		}
	}
	
	//1.第一行不翻转
	//2.枚举第一行的状态 2^15.....
	DFS(1,0);	DFS(1,1);
	
	if(jsx==true){
		for(int i=1;i<=H;++i){
			printf("%d",Ans.G[i][1]);
			for(int j=2;j<=L;++j){
				printf(" %d",Ans.G[i][j]);
			}
			printf("\n");
		}
	}
	else{
		printf("IMPOSSIBLE\n");
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}
请先登陆