编程题＃1： 画家问题
来源: POJ (Coursera声明：在POJ上完成的习题将不会计入Coursera的最后成绩。)
注意： 总时间限制: 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”。
样例输入
2 3 yyy yyy yyy 5 wwwww wwwww wwwww wwwww wwwww
样例输出
0 15
1 #include <iostream> 2 #include <math.h> 3 using namespace std; 4 int guess(int *puzzle, int *press,int i) 5 { 6 int c, r, count = 0; 7 for (c = 1; c < i+1; ++c) { 8 if (press[(i+2)+c] == 1) count++; 9 } 10 for (r=1; r< i; r++) { 11 for (c = 1; c < i+1; ++c) { 12 // 跟踪puzzle第一行，计算press其他行的值 13 press[(r + 1)* (i+2) +c] = (puzzle[r*(i+2)+c] + press[r*(i+2)+c] + press[(r - 1)*(i+2)+c] 14 + press[r*(i+2)+c - 1] + press[r*(i+2)+c + 1]) % 2; 15 if (press[(r + 1)* (i+2) +c] == 1) count++; 16 } 17 } 18 for (c=1; c < i + 1; c++) { 19 if ((press[i*(i+2)+c - 1] + press[i*(i+2)+c] + press[i*(i+2)+c + 1] + 20 press[(i - 1)*(i+2)+c]) % 2 != puzzle[i*(i + 2)+c]) { 21 return -1; // 返回-1标示该press的第一行不能使地板全变黄 22 } 23 24 } 25 return count;//如果能使地板全变黄，返回该办法所需涂的地砖的个数 26 } 27 28 int enumerate (int *puzzle, int *press,int i) 29 { 30 int c, sum = -1,n= (int)pow(2,i); 31 for ( c=1; c<i+1; c++) { 32 press[(i+2)+c] = 0; 33 } 34 if (guess(puzzle, press, i) != -1) { 35 sum = guess(puzzle, press, i); 36 } 37 while (n--) { 38 press[(i+2)+1]++; 39 c = 1; 40 while (press[(i+2)+c] > 1) { 41 press[(i+2)+c] = 0; 42 c++; 43 press[(i+2)+c]++; 44 } 45 if (guess(puzzle, press, i) != -1) { 46 if (sum == -1) { 47 sum = guess(puzzle, press, i); 48 } else if (guess(puzzle, press, i) < sum) { 49 sum = guess(puzzle, press, i); 50 } 51 } 52 } 53 return sum; 54 } 55 56 int main() 57 { 58 int cases,i; 59 cin>>cases; 60 while (cases--) { 61 cin>>i; 62 if (i == 1) { 63 char t; 64 cin >> t; 65 if (t == 'w') { 66 cout<<1<<endl; 67 } else { 68 cout<<0<<endl; 69 } 70 } else { 71 int *puzzle, *press; 72 puzzle = new int[(i+2)*(i+2)];//初始数组 73 press = new int[(i+2)*(i+2)];//按下状态，按下为1，未操作为0 74 //初始化press数组 75 int c, r; 76 for (r=0; r<i+1; r++) { 77 press[r*(i+2)] = press[r*(i+2)+i+1] = 0; 78 } 79 for (c=1; c<i+1; c++) { 80 press[c] = 0; 81 } 82 //输入数据 83 for(r=1; r<i+1; r++) { 84 for(c=1; c<i+1; c++) { 85 char t; 86 cin >> t; 87 if (t == 'w') { 88 puzzle[r*(i+2)+c] = 1; 89 } else { 90 puzzle[r*(i+2)+c] = 0; 91 } 92 } 93 } 94 int result = enumerate(puzzle,press,i); 95 if (result == -1) { 96 cout<<"inf"<<endl; 97 } else { 98 cout<<result<<endl; 99 } 100 } 101 102 } 103 104 return 0; 105 }