画家问题保姆级解题思路

大家好，欢迎来到IT知识分享网。

画家问题（题目源于北大百练）

在这里提供几组测试数据

下面进行解题环节

下面进行代码解读环节

1.主函数区域

int main(){ //信息初始化 int n; cin >> n; //scanf("%d",&n); //这是画板的行列数 //getchar(); 一定要吸收空格，否则就会读入到数组中 //创建二维数组储存初始画板信息,将w，y字母转化成0，1数字 char huaban[20][20]; for(int i = 1;i<=n;i++){ //留出第一行用来枚举 for(int j =0;j<n;j++){ //scanf("%c",&huaban[i][j]); cin >> huaban[i][j]; huaban[i][j]=(huaban[i][j]=='w')?'0':'1'; } //getchar(); //吸收回车字符 } //补充二进制0，1枚举行 Enum(huaban,n); //进行枚举操作，其他操作步骤都在这个函数中调用 return 0; } 

2.枚举区域和最终的输出

void Enum(char huaban[20][20],int n){ int chance = (int)pow(2,n); //这是枚举数据 利用十进制转换二进制 int num[1234]={0};//涂色次数储存器 char huaban1[20][20]; int yy = 0; for(int i = 0;i < chance; i++){ //十进制转二进制放到huaban第一行中 char bu[20]; for(int oi = 0;oi < 20; oi++) bu[oi]='0'; //可以保存0字符在数组 reverse(bu,i,n); for(int k = 0;k < n;k++){ huaban1[0][k]=bu[k]; } //在这一次的情况下去判断能否完成涂色任务并且记录步数 //把huaban1内的值保留一份利于每一种情况的使用 for(int i = 1;i <= n;i++){ //留出第一行用来枚举 for(int j = 0;j < n;j++){ huaban1[i][j]=huaban[i][j]; } } //输出区域 int t=task(huaban1,n); //在函数中huaban1传回保留值，每次无法恢复初始状态 if(t >= 0) { num[yy]=t; yy++; } } //看num中的最小值 if(yy == 0) printf("inf"); else printf("%d",min(num,yy)); } 

在这一块需要特别说明的就是进行涂色操作时要把原始画板数据放到一个新的数组中huaban1，因为数组传参在涂色操作时改变画板颜色，并进行保留，所以每次都要将原始画板数据huaban复制到待操作画板huaban1中

3.画板补充的第一行枚举数据

void reverse(char *bu,int i,int n){ int z = 0; while(i){ bu[z]=i%2+'0'; i/=2; z++; } } 

因为已经把bu数组中全部赋值为‘0’，所以没有改变的地方默认为‘0’，此外bu数组中的前后顺序与二进制的真实数据顺序是否相同没有用，因为所有情况都会罗列。

4.进行涂色任务

int task(char huaban1[20][20],int n){ //注意此时是n+1行，n列 //开始逐行去检索没涂色的地方 //如果没涂色，对下一行进行涂色操作 int count = 0;//涂色计数器 for(int zz=0;zz<n;zz++){ //最后一行不用涂色操作直接判定即可 for(int hh=0;hh<n;hh++){ if(huaban1[zz][hh]=='0'){ //进行涂色 if(hh==0){ huaban1[zz][hh]=huaban1[zz][hh]=='0'?'1':'0'; huaban1[zz+1][hh]=huaban1[zz+1][hh]=='0'?'1':'0'; if((zz+2)!=(n+1)) huaban1[zz+2][hh]=huaban1[zz+2][hh]=='0'?'1':'0'; huaban1[zz+1][hh+1]=huaban1[zz+1][hh+1]=='0'?'1':'0'; } else if(hh==(n-1)){ huaban1[zz][hh]=huaban1[zz][hh]=='0'?'1':'0'; huaban1[zz+1][hh]=huaban1[zz+1][hh]=='0'?'1':'0'; if((zz+2)!=(n+1)) huaban1[zz+2][hh]=huaban1[zz+2][hh]=='0'?'1':'0'; huaban1[zz+1][hh-1]=huaban1[zz+1][hh-1]=='0'?'1':'0'; } else if(zz==(n-1)){ huaban1[zz][hh]=huaban1[zz][hh]=='0'?'1':'0'; huaban1[zz+1][hh]=huaban1[zz+1][hh]=='0'?'1':'0'; huaban1[zz+1][hh-1]=huaban1[zz+1][hh-1]=='0'?'1':'0'; huaban1[zz+1][hh+1]=huaban1[zz+1][hh+1]=='0'?'1':'0'; } else{ huaban1[zz][hh]=huaban1[zz][hh]=='0'?'1':'0'; huaban1[zz+1][hh]=huaban1[zz+1][hh]=='0'?'1':'0'; huaban1[zz+1][hh-1]=huaban1[zz+1][hh-1]=='0'?'1':'0'; huaban1[zz+1][hh+1]=huaban1[zz+1][hh+1]=='0'?'1':'0'; huaban1[zz+2][hh]=huaban1[zz+2][hh]=='0'?'1':'0'; } count++; } } } //涂色结束，去判断最后一行是否全为1 int op; for(op = 0;op<n;op++){ if(huaban1[n][op]=='1') continue; else return -1; } return count; } 

这个地方我必须承认，涂色的操作确实有些麻烦了，这里之所以呈现出来，是想提醒各位，只要在写代码时这种机械性重复动作，一是要考虑下循环能不能用，二是要考虑我写个函数能不能代替，所以有简化版的涂色操作在文章最后面。

5.返回最小的操作步骤

int min(int num[],int yy){ int min1=num[0]; for(int ji = 1;ji < yy;ji++){ if(num[ji]<min1){ min1=num[ji]; } } return min1; } 

这个地方我也得承认，多余了，因为可以不用数组去储存这个画板的所有成功涂色步骤数，而是每次有步骤数值，就去比较，只保留最小值，直接进行输出。

呈现全部代码（较为多余版）

#include<stdio.h> #include<math.h> #include <cstring> #include <iostream> using namespace std; int min(int num[],int yy); int task(char huaban1[20][20],int n); void reverse(char *bu,int i,int n); void Enum(char huaban[20][20],int n); int main(){ //信息初始化 int n; cin >> n; //scanf("%d",&n); //这是画板的行列数 //getchar(); //一定要吸收空格，否则就会读入到数组中 //创建二维数组储存初始画板信息,将w，y字母转化成0，1数字 char huaban[20][20]; for(int i = 1;i<=n;i++){ //留出第一行用来枚举 for(int j =0;j<n;j++){ //scanf("%c",&huaban[i][j]); cin >> huaban[i][j]; huaban[i][j]=(huaban[i][j]=='w')?'0':'1'; } //getchar(); //吸收回车字符 } //补充二进制0，1枚举行 Enum(huaban,n); return 0; } void Enum(char huaban[20][20],int n){ int chance = (int)pow(2,n); int num[1234]={0};//涂色次数储存器 char huaban1[20][20]; int yy = 0; for(int i = 0;i < chance; i++){ //十进制转二进制放到huaban第一行中 char bu[20]; for(int oi = 0;oi < 20; oi++) bu[oi]='0'; //可以保存0字符在数组 reverse(bu,i,n); for(int k = 0;k < n;k++){ huaban1[0][k]=bu[k]; } //在这一次的情况下去判断能否完成涂色任务并且记录步数 //把huaban1内的值保留一份利于每一种情况的使用 for(int i = 1;i <= n;i++){ //留出第一行用来枚举 for(int j = 0;j < n;j++){ huaban1[i][j]=huaban[i][j]; } } int t=task(huaban1,n); //在函数中huaban1传回保留值，每次无法恢复初始状态 if(t >= 0) { num[yy]=t; yy++; } } //看num中的最小值 if(yy == 0) printf("inf"); else printf("%d",min(num,yy)); } void reverse(char *bu,int i,int n){ int z = 0; while(i){ bu[z]=i%2+'0'; i/=2; z++; } //反转补位 //for(int k = 0,j = (n-1);k < j;k++,j--){ // char temp = bu[k];bu[k]=bu[j];bu[j]=temp; //} } int task(char huaban1[20][20],int n){ //注意此时是n+1行，n列 //开始逐行去检索没涂色的地方 //如果没涂色，对下一行进行涂色操作 int count = 0;//涂色计数器 for(int zz=0;zz<n;zz++){ //最后一行不用涂色操作直接判定即可 for(int hh=0;hh<n;hh++){ if(huaban1[zz][hh]=='0'){ //进行涂色 if(hh==0){ huaban1[zz][hh]=huaban1[zz][hh]=='0'?'1':'0'; huaban1[zz+1][hh]=huaban1[zz+1][hh]=='0'?'1':'0'; if((zz+2)!=(n+1)) huaban1[zz+2][hh]=huaban1[zz+2][hh]=='0'?'1':'0'; huaban1[zz+1][hh+1]=huaban1[zz+1][hh+1]=='0'?'1':'0'; } else if(hh==(n-1)){ huaban1[zz][hh]=huaban1[zz][hh]=='0'?'1':'0'; huaban1[zz+1][hh]=huaban1[zz+1][hh]=='0'?'1':'0'; if((zz+2)!=(n+1)) huaban1[zz+2][hh]=huaban1[zz+2][hh]=='0'?'1':'0'; huaban1[zz+1][hh-1]=huaban1[zz+1][hh-1]=='0'?'1':'0'; } else if(zz==(n-1)){ huaban1[zz][hh]=huaban1[zz][hh]=='0'?'1':'0'; huaban1[zz+1][hh]=huaban1[zz+1][hh]=='0'?'1':'0'; huaban1[zz+1][hh-1]=huaban1[zz+1][hh-1]=='0'?'1':'0'; huaban1[zz+1][hh+1]=huaban1[zz+1][hh+1]=='0'?'1':'0'; } else{ huaban1[zz][hh]=huaban1[zz][hh]=='0'?'1':'0'; huaban1[zz+1][hh]=huaban1[zz+1][hh]=='0'?'1':'0'; huaban1[zz+1][hh-1]=huaban1[zz+1][hh-1]=='0'?'1':'0'; huaban1[zz+1][hh+1]=huaban1[zz+1][hh+1]=='0'?'1':'0'; huaban1[zz+2][hh]=huaban1[zz+2][hh]=='0'?'1':'0'; } count++; } } } //涂色结束，去判断最后一行是否全为1 int op; for(op = 0;op<n;op++){ if(huaban1[n][op]=='1') continue; else return -1; } return count; } int min(int num[],int yy){ int min1=num[0]; for(int ji = 1;ji < yy;ji++){ if(num[ji]<min1){ min1=num[ji]; } } return min1; } 

补充代码的优化方案

关于涂色操作的简化：

for(int zz=0;zz<n;zz++){ //最后一行不用涂色操作直接判定即可 for(int hh=0;hh<n;hh++){ if(huaban1[zz][hh]=='0'){ //进行涂色 Easytask(zz+1,hh , n , huaban1);//以（zz+1，h）为涂色中心 count++; } } } //再写一个新函数进行涂色操作 void Easytask(int i, int j , int n, char huaban1[20][20]){ change(i , j , n , huaban1); change(i , j + 1, n ,huaban1); change(i , j - 1 , n ,huaban1); change(i - 1 , j , n ,huaban1); change(i + 1 , j , n ,huaban1); } //再加一个函数进行判断该区域是否越界 void change(int i , int j , int n , char huaban1[20][20]){ if(i >= 0 && i <= n && j >= 0 && j < n){ //不用分情况讨论，只要在画板里就能改变 huaban1[i][j] = (huaban1[i][j] == '0') ? '1' : '0'; } }