题目链接：
NOI题库： http://noi.openjudge.cn/ch0201/1815/
poj 1681： http://poj.org/problem?id=1681
- 总时间限制: 1000ms内存限制: 65536kB
- 描述
-
有一个正方形的墙，由N*N个正方形的砖组成，其中一些砖是白色的，另外一些砖是黄色的。Bob是个画家，想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i, j)个位置的砖时， 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖，才能使所有砖的颜色都变成黄色。
输入第一行是一个整数n (1≤n ≤15)，表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖，“y”表示黄砖。输出一行，如果Bob能够将所有的砖都涂成黄色，则输出最少需要涂画的砖数，否则输出“inf”。样例输入
5 wwwww wwwww wwwww wwwww wwwww
样例输出
15
算法分析：
这个题目有些像熄灯问题，解法也是利用了熄灯问题中第一行的选择决定下一行的选择。所以只需要枚举出第一行所有的操作方案，以及验证最后一行是否正确。
大体思路：枚举第一行的所有可能的操作方案。对每一个方案都要统计一下该方案需要涂的方块数目并检验该方案能否使得所有的方块最后都变为黄色。检验方法就是扫描最后一行是否剩余白色块即可。
代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<limits.h> 4 5 int n; 6 char src[18][18],temp1[18][18]; 7 int dx[4]={-1,0,1,0};//上右下左 8 int dy[4]={0,1,0,-1}; 9 10 int GetBit(int c,int i)//取c的第i位。i从0开始。 11 { return ( c >> i ) & 1; } 12 void Flip(int i,int j)//将src[i][j]及其周围元素取反 13 { 14 int k,x,y; 15 src[i][j]=src[i][j]=='w'?'y':'w'; 16 for(k=0;k<4;k++) 17 { 18 x=i+dx[k]; 19 y=j+dy[k]; 20 if(x>=0&&x<n&&y>=0&&y<n) 21 { 22 src[x][y]=src[x][y]=='w'?'y':'w'; 23 } 24 } 25 } 26 int main(int argc, char *argv[]) 27 { 28 int i,j,k,t; 29 char str[20]; 30 int count,min=INT_MAX; 31 32 scanf("%d",&n); 33 for(i=0;i<n;i++) 34 { 35 scanf("%s",str); 36 for(j=0;j<n;j++) 37 { 38 temp1[i][j]=src[i][j]=str[j]; 39 } 40 } 41 42 t=(1<<n);//第0行总共有2^n种不同的涂法 43 for(i=0;i<=t;i++)//枚举所有涂法，对每一种涂法都统计该方案需要涂的数量并检验该方案能否全变为y。 44 { 45 memcpy(src,temp1,sizeof(src)); 46 /*for(k=0;k<n;k++) 47 for(j=0;j<n;j++) 48 src[k][j]=temp1[k][j];*/ 49 count=0; 50 51 for(j=0;j<n;j++)//根据当前方案i各个比特的值去涂第0行 52 { 53 if(GetBit(i,j)==1)//获取i的第j个比特。若为1，则需要涂（0，j）位置 54 { 55 Flip(0,j); 56 count++; 57 } 58 } 59 for(k=1;k<n;k++)//扫描除了第0行以外的所有行 60 { 61 for(j=0;j<n;j++) 62 { 63 if(src[k-1][j]=='w') 64 { 65 Flip(k,j); 66 count++; 67 } 68 } 69 } 70 for(j=0;j<n;j++)//扫描最后一行检查是否有未变为y的单元 71 { 72 if(src[n-1][j]=='w') break; 73 } 74 if(j==n&&count<min) min=count; 75 } 76 if(min==INT_MAX) printf("inf\n"); 77 else printf("%d\n",min); 78 return 0; 79 }
poj提交的代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<limits.h> 4 5 int n; 6 char src[18][18],temp1[18][18]; 7 int dx[4]={-1,0,1,0};//上右下左 8 int dy[4]={0,1,0,-1}; 9 10 int GetBit(int c,int i)//取c的第i位。i从0开始。 11 { return ( c >> i ) & 1; } 12 void Flip(int i,int j)//将src[i][j]及其周围元素取反 13 { 14 int k,x,y; 15 src[i][j]=src[i][j]=='w'?'y':'w'; 16 for(k=0;k<4;k++) 17 { 18 x=i+dx[k]; 19 y=j+dy[k]; 20 if(x>=0&&x<n&&y>=0&&y<n) 21 { 22 src[x][y]=src[x][y]=='w'?'y':'w'; 23 } 24 } 25 } 26 int main(int argc, char *argv[]) 27 { 28 int i,j,k,t; 29 char str[20]; 30 int count,min=INT_MAX; 31 32 int T; 33 scanf("%d",&T); 34 for(;T>0;T--) 35 { 36 min=INT_MAX; 37 scanf("%d",&n); 38 for(i=0;i<n;i++) 39 { 40 scanf("%s",str); 41 for(j=0;j<n;j++) 42 { 43 temp1[i][j]=src[i][j]=str[j]; 44 } 45 } 46 47 t=(1<<n);//第0行总共有2^n种不同的涂法 48 for(i=0;i<=t;i++)//枚举所有涂法，对每一种涂法都统计该方案需要涂的数量并检验该方案能否全变为y。 49 { 50 memcpy(src,temp1,sizeof(src)); 51 /*for(k=0;k<n;k++) 52 for(j=0;j<n;j++) 53 src[k][j]=temp1[k][j];*/ 54 count=0; 55 56 for(j=0;j<n;j++)//根据当前方案i各个比特的值去涂第0行 57 { 58 if(GetBit(i,j)==1)//获取i的第j个比特。若为1，则需要涂（0，j）位置 59 { 60 Flip(0,j); 61 count++; 62 } 63 } 64 for(k=1;k<n;k++)//扫描除了第0行以外的所有行 65 { 66 for(j=0;j<n;j++) 67 { 68 if(src[k-1][j]=='w') 69 { 70 Flip(k,j); 71 count++; 72 } 73 } 74 } 75 for(j=0;j<n;j++)//扫描最后一行检查是否有未变为y的单元 76 { 77 if(src[n-1][j]=='w') break; 78 } 79 if(j==n&&count<min) min=count; 80 } 81 if(min==INT_MAX) printf("inf\n"); 82 else printf("%d\n",min); 83 } 84 return 0; 85 }
