1.链接地址：
http://bailian.openjudge.cn/practice/2813
http://poj.org/problem?id=1681
2.题目：
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 有一个正方形的墙，由N*N个正方形的砖组成，其中一些砖是白色的，另外一些砖是黄色的。Bob是个画家，想把全部的砖都涂成黄色。但他的画 笔不好使。当他用画笔涂画第(i, j)个位置的砖时， 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖，才能使所有砖的颜色都变成黄色。
- 输入
- 第一行是个整数t(1≤t ≤20)，表示要测试的案例数。然后是t个案例。每个案例的首行是一个整数n (1≤n ≤15)，表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白 砖，“y”表示黄砖。
- 输出
- 每个案例输出一行。如果Bob能够将所有的砖都涂成黄色，则输出最少需要涂画的砖数，否则输出“inf”。
- 样例输入
- 样例输出
- 来源
- 1681
3.思路：
此题思路与 OpenJudge 2811 熄灯问题 和 Poj 1222 EXTENDED LIGHTS OUT 一样，请查看以下
http://www.cnblogs.com/mobileliker/p/3548190.html
注意此题的区别是有可能出现不存在的情况，所以要多一个判断
4.代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <string> 5 #include <cstring> 6 7 using namespace std; 8 9 int main() 10 { 11 int i,j; 12 13 int t; 14 cin>>t; 15 16 int n; 17 int flag; 18 while(t--) 19 { 20 flag = 1; 21 cin>>n; 22 23 bool *arr_draw = new bool[(n + 2) * (n + 2)]; 24 bool *arr_draw_save = new bool[(n + 2) * (n + 2)]; 25 bool *arr_res = new bool[(n + 2) * (n + 2)]; 26 27 string str; 28 memset(arr_draw,0,sizeof(bool) * (n + 2) * (n + 2)); 29 for(i = 1; i <= n; ++i) 30 { 31 cin>>str; 32 for(j = 1; j <= n; ++j) 33 { 34 if(str[j-1] == 'y') arr_draw[i * (n + 2) + j] = false; 35 else arr_draw[i * (n + 2) + j] = true; 36 } 37 } 38 memcpy(arr_draw_save,arr_draw,sizeof(bool) * (n + 2) * (n + 2)); 39 40 memset(arr_res + 1 * (n + 2),0,sizeof(bool) * (n + 2)); 41 while(1) 42 { 43 for(i = 1; i <= n; ++i) 44 { 45 for(j = 1; j <= n; ++j) 46 { 47 arr_draw[(i - 1) * (n + 2) + j] ^= arr_res[i * (n + 2) + j]; 48 arr_draw[i * (n + 2) + (j - 1)] ^= arr_res[i * (n + 2) + j]; 49 arr_draw[i * (n + 2) + (j + 1)] ^= arr_res[i * (n + 2) + j]; 50 arr_draw[(i + 1) * (n + 2) + j] ^= arr_res[i * (n + 2) + j]; 51 arr_draw[i * (n + 2) + j] ^= arr_res[i * (n + 2) + j]; 52 } 53 memcpy(&arr_res[(i + 1) * (n + 2)],&arr_draw[i * (n + 2)],sizeof(bool) * (n + 2)); 54 } 55 for(i = 1; i <= n; ++i) if(arr_draw[n * (n + 2) + i]) break; 56 if(i > n) break; 57 else 58 { 59 memcpy(arr_draw,arr_draw_save,sizeof(bool) * (n + 2) * (n + 2)); 60 61 for(i = n; i > 0; --i) if(!arr_res[1 *(n + 2) + i]) break; 62 while(i <= n) {arr_res[1 * (n + 2) + i] = !arr_res[1 * (n + 2) + i]; ++i;} 63 64 for(i = 1; i <= n; ++i) {if(arr_res[1 * (n + 2) + i]) break;} 65 if(i > n) {flag = 0; break;} 66 } 67 } 68 69 int count = 0; 70 if(flag) 71 { 72 for(i = 1; i <= n; ++i) 73 { 74 for(j = 1; j <= n; ++j) 75 { 76 count += arr_res[i * (n + 2) + j]; 77 } 78 } 79 cout<<count<<endl; 80 } 81 else cout<<"inf"<<endl; 82 83 delete [] arr_draw; 84 delete [] arr_draw_save; 85 delete [] arr_res; 86 87 } 88 return 0; 89 }