欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

2813:画家问题

程序员文章站 2022-09-15 21:51:32
这个题目和熄灯问题很类似,都是使用枚举的方法来解决,主要思想是枚举第一行,然后让第二行去匹配第一行,以此类推,一直到第n行,然后判断第n行的情况,如果符合条件,那就是合适的解。下面是一些关键的思想的详细解释: 首先,对于每一行是否涂画的操作:0表示不涂画,1表示涂画。press[ii+1][jj]= ......

  这个题目和熄灯问题很类似,都是使用枚举的方法来解决,主要思想是枚举第一行,然后让第二行去匹配第一行,以此类推,一直到第n行,然后判断第n行的情况,如果符合条件,那就是合适的解。下面是一些关键的思想的详细解释:

  首先,对于每一行是否涂画的操作:0表示不涂画,1表示涂画。press[ii+1][jj]=(press[ii][jj]+press[ii-1][jj]+press[ii][jj-1]+press[ii][jj+1]+start[ii][jj])%2;

  对最后一行的判断:if((press[n][jj]+press[n][jj-1]+press[n][jj+1]+press[n-1][jj])%2!=start[n][jj])

 题目和代码如下:

2813:画家问题

总时间限制: 
1000ms
 
内存限制: 
65536kB
描述

有一个正方形的墙,由N*N个正方形的砖组成,其中一些砖是白色的,另外一些砖是黄色的。Bob是个画家,想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i, j)个位置的砖时, 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖,才能使所有砖的颜色都变成黄色。

2813:画家问题
输入
第一行是一个整数n (1≤n ≤15),表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖,“y”表示黄砖。
输出
一行,如果Bob能够将所有的砖都涂成黄色,则输出最少需要涂画的砖数,否则输出“inf”。
样例输入
5
wwwww
wwwww
wwwww
wwwww
wwwww
样例输出
15 

#include<stdio.h>
#include<iostream>
using namespace std;
bool IsAllOne(int * s,int n){
	for(int i=1;i<n+1;i++)
	{
		if(s[i]==0)
			return false;
	}
	return true;
}
void switch01(int & i){
	if(i==0)
		i=1;
	else
		i=0;
}
int main(){
	int n;
	cin>>n;
	int start[n+1][n+2];
	for(int i=0;i<n+2;i++){
		start[0][i]=1;
	}
	for(int i=0;i<n+1;i++){
		start[i][0]=1;
	}
	for(int i=0;i<n+1;i++){
		start[i][n+1]=1;
	}
	for(int i=1;i<n+1;i++){
		string temps="";
		cin>>temps;
		for(int j=0;j<n;j++){
			if(temps[j]=='w'){
				start[i][j+1]=1;
			}else
				start[i][j+1]=0;
		}
	}
	int i=1;
	int press[n+1][n+2];
	for(int i=0;i<n+1;i++){
		for(int j=0;j<n+2;j++)
			press[i][j]=0;
	}
	int count=32767; 
	while(1){
		int temp_count=-1;
		for(int ii=1;ii<n;ii++){
			for(int jj=1;jj<n+1;jj++){
				press[ii+1][jj]=(press[ii][jj]+press[ii-1][jj]+press[ii][jj-1]+press[ii][jj+1]+start[ii][jj])%2;
			}
		}
		int flag=1;//0:failture,1 success
		for(int jj=1;jj<n+1;jj++){
			if((press[n][jj]+press[n][jj-1]+press[n][jj+1]+press[n-1][jj])%2!=start[n][jj]){
				flag=0;
				break;
			}
		}
		if(flag==1){
			for(int i=0;i<n+1;i++){
				for(int j=1;j<n+1;j++){
					//cout<<press[i][j]<<" ";
					if(press[i][j]){
						/*switch01(start[i][j]);
						if(j<n+1)	switch01(start[i][j+1]);
						if(j>0)	switch01(start[i][j-1]);
						if(i>0) switch01(start[i-1][j]);
						if(j<n) switch01(start[i+1][j]);*/
						if(temp_count<0)
						{
							temp_count=1;
						}else
							temp_count++;
					}
				}
				//cout<<endl;
			}
			if(temp_count==-1) temp_count=0;
			if(temp_count<count)
				count=temp_count;
			break;
		}	
		if(IsAllOne(press[1],n))
			break;
		press[1][1]+=1;
		int j=1;
		while(press[1][j]>=2){
			press[1][j]=0;
			press[1][j+1]+=1;
			j++;
		}
	}
	if(count==32767){
		cout<<"inf"<<endl;
	}else{
		cout<<count<<endl;
	}
	return 0;
}