2813:画家问题
总时间限制: 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
来源
1681
问题链接：Bailian2813 画家问题
问题简述：（略）
问题分析：这个问题与参考链接可以说是同一个问题，只是输入输出不同。解题代码是使用那个代码修改而来，同样采用暴力法实现。
数据表示方面，使用数组press[][]来存储开关按下标记。需要扩充1行即下标为0的行，需要扩充2列即下标为0的列和下标为7的列。press[i][j]=1表示第i行第j列需要按下，press[i][j]=0表示第i行第j列不需要按下。
采用逐行枚举的方法来实现。对第一行进行枚举，枚举所有的可能（000000-111111），开始时先看第一行为000000（都不按按钮）的情况，然后采用逐步加1的方式来实现。
首先需要关掉第i行的灯，可以通过按第i+1行来实现。一般而言，若b[i][j]灯亮，则需要按b[i+1][j]。这样，可以采用从第2行开始，逐行递推进行暴力枚举方法来解决。
另外，press[i][j]值由初始灯的状态，和前面行按按钮的情况算出。
程序说明：（略）
参考链接：Bailian2811 熄灯问题【暴力】
题记：（略）
AC的C++语言程序如下：
1/* Bailian2813 画家问题 */ 2 3#include <bits/stdc++.h> 4 5using namespace std; 6 7const int N = 15; 8char g[N + 1][N + 2]; 9int b[N + 1][N + 2], press[N + 1][N + 2]; 10int ans; 11 12void solve(int n) 13{ 14 for(int i = 2 ; i <= n; i++) { 15 for(int j = 1 ; j <= n; j++) { 16 press[i][j] = (b[i - 1][j] + press[i - 1][j] + press[i - 1][j - 1] + press[i - 2][j] + press[i - 1][j + 1]) % 2; 17 18 } 19 } 20 21 /* 检查最后一行是否都已经关灯 */ 22 bool flag = true; 23 for(int j = 1 , i = n + 1; j <= n ; j++) { 24 int t = (b[i - 1][j] + press[i - 1][j] + press[i - 1][j - 1] + press[i - 2][j] + press[i - 1][j + 1]) % 2; 25 if(t) {flag = false; break;} 26 } 27 28 if(flag) { 29 int cnt = 0; 30 for(int i = 1 ; i <= n; i++) 31 for(int j = 1 ; j <= n; j++) 32 if(press[i][j]) cnt++; 33 ans = min(ans, cnt); 34 } 35} 36 37int main() 38{ 39 int n; 40 scanf("%d", &n); 41 getchar(); 42 for(int i = 1; i <= n; i++) 43 scanf("%s", g[i] + 1); 44 45 for(int i = 1; i <= n; i++) 46 for(int j = 1; j <= n; j++) 47 if(g[i][j] == 'w') b[i][j] = 1; 48 else if(g[i][j] == 'y') b[i][j] = 0; 49 50 51 memset(press, 0, sizeof(press)); 52 ans = n * n + 1; 53 for(;;) { 54 solve(n); 55 56 /* 对于第1行进行枚举，000000-111111，采用加1方式实现 */ 57 int t = 1; 58 press[1][t]++; 59 while(press[1][t] > 1) { 60 press[1][t] = 0; 61 t++; 62 press[1][t]++; 63 } 64 if(t > n) break; 65 } 66 67 if(ans == n * n + 1) 68 printf("inf\n"); 69 else 70 printf("%d\n", ans); 71 72 return 0; 73} 74 75/* 765 77wwwww 78wwwww 79wwwww 80wwwww 81wwwww 825 83ywyyy 84wwwyy 85ywyyy 86yyyyy 87yyyyy 885 89ywyyy 90wwyyy 91yywwy 92yywyy 93yyyyy 94 955 96ywwwy 97yywyy 98yyyyy 99yyyyy 100yyyyy 1015 102wyywy 103ywwyy 104yyyyy 105yyyyy 106yyyyy 1075 108wywyw 109ywwwy 110yyyyy 111yyyyy 112yyyyy 1135 114wwwww 115wywyw 116ywywy 117yyyyy 118yyyyy 1195 120wwwww 121wwwww 122wyyyw 123ywywy 124yyyyy 1255 126wwwww 127wwwww 128wwyww 129wyyyw 130ywywy 1315 132wwwww 133wwwww 134wwwww 135wwwww 136ywwwy 137 138*/