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++语言程序如下：
/* Bailian2813 画家问题 */ #include <bits/stdc++.h> using namespace std; const int N = 15; char g[N + 1][N + 2]; int b[N + 1][N + 2], press[N + 1][N + 2]; int ans; void solve(int n) { for(int i = 2 ; i <= n; i++) { for(int j = 1 ; j <= n; j++) { 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; } } /* 检查最后一行是否都已经关灯 */ bool flag = true; for(int j = 1 , i = n + 1; j <= n ; j++) { 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; if(t) {flag = false; break;} } if(flag) { int cnt = 0; for(int i = 1 ; i <= n; i++) for(int j = 1 ; j <= n; j++) if(press[i][j]) cnt++; ans = min(ans, cnt); } } int main() { int n; scanf("%d", &n); getchar(); for(int i = 1; i <= n; i++) scanf("%s", g[i] + 1); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(g[i][j] == 'w') b[i][j] = 1; else if(g[i][j] == 'y') b[i][j] = 0; memset(press, 0, sizeof(press)); ans = n * n + 1; for(;;) { solve(n); /* 对于第1行进行枚举，000000-111111，采用加1方式实现 */ int t = 1; press[1][t]++; while(press[1][t] > 1) { press[1][t] = 0; t++; press[1][t]++; } if(t > n) break; } if(ans == n * n + 1) printf("inf\n"); else printf("%d\n", ans); return 0; } /* 5 wwwww wwwww wwwww wwwww wwwww 5 ywyyy wwwyy ywyyy yyyyy yyyyy 5 ywyyy wwyyy yywwy yywyy yyyyy 5 ywwwy yywyy yyyyy yyyyy yyyyy 5 wyywy ywwyy yyyyy yyyyy yyyyy 5 wywyw ywwwy yyyyy yyyyy yyyyy 5 wwwww wywyw ywywy yyyyy yyyyy 5 wwwww wwwww wyyyw ywywy yyyyy 5 wwwww wwwww wwyww wyyyw ywywy 5 wwwww wwwww wwwww wwwww ywwwy */
