noj 1042 改棋盘.txt

ACM资料大集合

#include <stdio.h> 
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

//NOJ 1042 改棋盘
//假设法

#define NMAX 17
#define MAX 500
//定义修改格子的意思
#define CHN tqizi[hang-1][lie]=(tqizi[hang-1][lie]+1)%2
#define CHS tqizi[hang+1][lie]=(tqizi[hang+1][lie]+1)%2
#define CHE tqizi[hang][lie+1]=(tqizi[hang][lie+1]+1)%2
#define CHW tqizi[hang][lie-1]=(tqizi[hang][lie-1]+1)%2
#define CHM tqizi[hang][lie]=(tqizi[hang][lie]+1)%2
int qizi[NMAX][NMAX];
int done[NMAX][NMAX];
int final[NMAX][NMAX];
int tqizi[NMAX][NMAX];//第i次假设第1行修改情况时，棋盘的情况

void change(int hang,int lie,int hnum,int lnum)
{
	CHM;//本身的格子肯定要改
	//周围的格子根据边界情况修改
	if(1!=hang&&hnum!=hang&&1!=lie&&lnum!=lie) {CHN;CHS;CHE;CHW;return;}
	else if(hang==1&&lie==1) {CHS; CHE; return;}
	else if(hang==1&&lie==lnum) {CHS; CHW; return;}
	else if(hang==hnum&&lie==1) {CHN; CHE; return;}
	else if(hang==hnum&&lie==lnum) {CHN; CHW; return;}
	else if(hang==1) {CHS;CHW;CHE;}
	else if(hang==hnum) {CHN;CHW;CHE;}
	else if(lie==1) {CHN;CHS;CHE;}
	else if(lie==lnum) {CHN;CHS;CHW;}
} 

void print(int hnum,int lnum)
{	//第i次假设第1行修改情况时，打印棋盘的移动情况
	int i,j;
	for(i=1;i<=hnum;i++)
	{
		for(j=1;j<=lnum;j++)
			cout<<done[i][j]<<" ";
		cout<<endl;
	}
//	system("pause");
}
int cal(int hnum,int lnum)
{
	int asume,i,j,k,tt,shuzu[NMAX],win,min,cishu,p,q;
	asume=pow(2,lnum);
	win=0;
	min=MAX;
	memset(final,0,sizeof(final));
	for(i=0;i<asume;i++)
	{	//第i次假设第1行修改情况
		for(p=1;p<=hnum;p++)
			for(q=1;q<=lnum;q++)
				tqizi[p][q]=qizi[p][q];
		cishu=0;
		memset(done,0,sizeof(done));
		j=lnum-1;
		tt=i;
		while(j>=0)
		{//利用二进制数存储第i次时，第1行应该如何修改
			shuzu[j]=tt%2;
			tt/=2;
			j--;
		}
		for(j=0;j<lnum;j++)
		{
			if(shuzu[j]==1) 
			{	//如果二进制的某数位上为1，则修改改位
				change(1,j+1,hnum,lnum);
				done[1][j+1]=1;//标记修改
				cishu++;//修改次数加1
			}
		}
		for(j=2;j<=hnum;j++)
		{	//剩下的j-1行，要根据上一行的情况进行修改
			for(k=1;k<=lnum;k++)
			{
				if(tqizi[j-1][k]==1) 
				{	//上一行的同一列上为1时，肯定要对改位修改
					change(j,k,hnum,lnum);
					done[j][k]=1;
					cishu++;
				}
			}
		}
		for(j=1;j<=lnum;j++)
		{	
			if(tqizi[hnum][j]==1) break;
		}
//		cout<<"i="<<i<<endl;
//		print(hnum,lnum);
		if(j>lnum) 
		{	//只有当最后一列都为1时，表示一开始对第1行的假设是可行的
			if(min>cishu) 
			{	//取最小的次数
				min=cishu;
				for(p=1;p<=hnum;p++)
				{
					for(q=1;q<=lnum;q++)
						final[p][q]=done[p][q];//final[][]为最后的修改结果
				}

			}
			win=1;
		}
	}
	return win;
}

int main()
{
	int i,j,hnum,lnum;
	while(scanf("%d%d",&hnum,&lnum)!=EOF)
	{
	for(i=1;i<=hnum;i++)
	{
		for(j=1;j<=lnum;j++)
			scanf("%d",&qizi[i][j]);
	}
	if(cal(hnum,lnum)==0) cout<<"IMPOSSIBLE"<<endl;
	else
	{
		for(i=1;i<=hnum;i++)
		{
			for(j=1;j<=lnum;j++)
				printf("%d ",final[i][j]);
			cout<<endl;
		}
	}
	}
	return 0;
}