题目大意：农夫想要测牛的智商，于是他把牛带到一个黑白格子的地，专门来踩格子看他们能不能把格子踩称全白
这一题其实就是一个枚举题，只是我们只用枚举第一行就可以了，因为这一题有点像开关一样，一个翻了，另一个就要跟着一起翻，第一行会影响下面所有行，而且影响情况只有一种，所以枚举完了以后我们不断模拟就可以了
1 #include <iostream> 2 #include <functional> 3 #include <algorithm> 4 5 using namespace std; 6 7 static int map[18][18], flip[18][18], ans_map[18][18], M, N; 8 static int dirx[4] = { -1, 0, 0, 1 }; 9 static int diry[4] = { 0, -1, 0, 0 }; 10 11 int solve(void); 12 int get_color(const int, const int); 13 14 int main(void)//开关问题，枚举第一行即可得到下面几行的关系 15 { 16 int ans, tmp; 17 while (~scanf("%d%d", &N, &M))//读图 18 { 19 for (int i = 0; i < N; i++) 20 for (int j = 0; j < M; j++) 21 scanf("%d", &map[i][j]); 22 ans = INT_MAX; 23 for (int i = 0; i < 1 << M; i++)//枚举第一行 24 { 25 memset(flip, 0, sizeof(flip)); 26 for (int j = 0; j < M; j++)//枚举结果填入第一行 27 if ((1 << j & i) != 0) 28 flip[0][M - j - 1] = 1; 29 tmp = solve(); 30 if (tmp >= 0 && tmp < ans) 31 { 32 ans = tmp; 33 memcpy(ans_map, flip, sizeof(flip)); 34 } 35 } 36 37 if (ans == INT_MAX) 38 printf("IMPOSSIBLE "); 39 else 40 { 41 for (int i = 0; i < N; i++) 42 { 43 for (int j = 0; j < M; j++) 44 printf("%d ",ans_map[i][j]); 45 printf(" "); 46 } 47 } 48 } 49 return 0; 50 } 51 52 int solve(void) 53 { 54 int ans = 0; 55 for (int i = 1; i < N; i++)//从第二行开始一行一行模拟 56 for (int j = 0; j < M; j++) 57 if (get_color(j, i - 1) == 1)//记住是上一行翻的牌子 58 flip[i][j] = 1;//说明需要翻 59 60 for (int j = 0; j < M; j++)//得到最后一行的所有格子的颜色，如果还有黑色，则说明这一步无法把格子全部翻转成白色 61 if (get_color(j, N - 1) == 1) 62 return -1; 63 64 for (int i = 0; i < N; i++)//统计步数 65 for (int j = 0; j < M; j++) 66 if (flip[i][j]) 67 ans++; 68 return ans; 69 } 70 71 int get_color(const int x, const int y) 72 { 73 //得到(x,y)位置的颜色 74 int ny, nx, sum = map[y][x]; 75 76 for (int i = 0; i < 4; i++) 77 { 78 nx = x + dirx[i]; ny = y + diry[i]; 79 if ((0 <= nx&&nx < M) && (0 <= ny&&ny < N)) 80 sum += flip[ny][nx]; 81 } 82 return sum % 2; 83 }
