首页 > 代码库 > POJ 3279 Fliptile
POJ 3279 Fliptile
//这道题还是很有意思
//最开始无从下手但是 可以发现 翻牌和先后顺序无关 ---> 那么只能翻1次或不翻 因为其他情况和1 0 都是重复的
//那么 如果强行枚举就是2^n
//这里就没有想到了 ------->降维度的简化
//确定第一行后 第二行就要把第一行的1都翻为0 才能继续下去 所以第二行事实是确定的
//以此类推 如果最后一行都为0则成立否则 失败
//那么只需要枚举第一行的情况 1e4的复杂度 很小
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <queue> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #define READ() freopen("in.txt", "r", stdin); 9 #define WRITE() freopen("out.txt", "w", stdout); 10 #define INF 0x3f3f3f3f 11 12 using namespace std; 13 14 int M, N; 15 int maze[28][28], mazecp[28][28]; 16 int perm[28], num = 0; 17 set<string> s; 18 int d[4][2] = 19 { 20 -1, 0, 21 0, 1, 22 1, 0, 23 0, -1 24 }; 25 char operation[28][28]; 26 char ans_operation[28][28]; 27 int tmp_ans = 0, ans = INF; 28 29 bool OK(int x, int y) 30 { 31 if (x < 0|| x >= M || y < 0 || y >= N) return false; 32 return true; 33 } 34 35 36 void dfs(int x)//x表示现在在第几列 37 { 38 if (x == N)//最后一列已经决定翻完 39 { 40 //先把第一行的翻完 41 tmp_ans = 0; 42 for (int i = 0; i < N; i++) 43 { 44 if (operation[0][i] == ‘1‘) 45 { 46 tmp_ans++; 47 mazecp[0][i] += 1; 48 for (int p = 0; p < 4; p++) 49 { 50 int nx = 0+d[p][0], ny = i+d[p][1]; 51 if (OK(nx, ny)) 52 { 53 mazecp[nx][ny] += 1; 54 } 55 } 56 } 57 } 58 //第一行确定 其余所有行都确定 59 for (int i = 1; i < M; i++) 60 { 61 for (int j = 0; j < N; j++) 62 { 63 if (mazecp[i-1][j] % 2 == 1) 64 { 65 operation[i][j] = ‘1‘;//那么这一个就要翻 66 tmp_ans++; 67 mazecp[i][j] += 1; 68 for (int p = 0; p < 4; p++)//造成的影响 69 { 70 int nx = i+d[p][0], ny = j+d[p][1]; 71 if (OK(nx, ny)) 72 { 73 mazecp[nx][ny] += 1; 74 } 75 } 76 } 77 } 78 } 79 //检查最后一行是否为 都为偶数 80 bool success = true; 81 for (int i = 0; i < N; i++) 82 { 83 if (mazecp[M-1][i] % 2 == 1) 84 { 85 success = false; 86 break; 87 } 88 } 89 if (success) 90 { 91 if (tmp_ans < ans)//要先保证翻的次数最少 然后是最小字典序 哎 坑了 92 { 93 ans = tmp_ans; 94 for (int i = 0; i < M; i++) 95 { 96 for (int j = 0; j < N; j++) ans_operation[i][j] = operation[i][j]; 97 } 98 } 99 else if (tmp_ans == ans) 100 { 101 if (strcmp(ans_operation[0], operation[0]) > 0) 102 { 103 for (int i = 0; i < M; i++) 104 for (int j = 0; j < N; j++) ans_operation[i][j] = operation[i][j]; 105 } 106 }//成功 107 } 108 for (int i = 1; i < M; i++) fill(operation[i], operation[i]+N, ‘0‘);//重置操作 109 for (int i = 0; i < M; i++) 110 { 111 for (int j = 0; j < N; j++) mazecp[i][j] = maze[i][j];//重置地图 112 } 113 return ; 114 } 115 operation[0][x] = ‘0‘; 116 dfs(x+1); 117 operation[0][x] = ‘1‘; 118 dfs(x+1); 119 return ; 120 } 121 122 int main() 123 { 124 //READ() 125 //WRITE() 126 while(~scanf("%d%d", &M, &N)) 127 { 128 for (int i = 0; i < M; i++) 129 { 130 for (int j = 0; j < N; j++) 131 { 132 scanf("%d", &maze[i][j]); 133 mazecp[i][j] = maze[i][j]; 134 } 135 } 136 memset(operation, ‘0‘, sizeof(operation)); 137 memset(ans_operation, ‘1‘, sizeof(ans_operation)); 138 ans = INF; 139 dfs(0); 140 if (ans < INF) 141 { 142 for (int i = 0; i < M; i++) 143 { 144 for (int j = 0; j < N; j++) 145 { 146 printf("%c ", ans_operation[i][j]); 147 } 148 putchar(‘\n‘); 149 } 150 } 151 else printf("IMPOSSIBLE\n"); 152 } 153 return 0; 154 }
POJ 3279 Fliptile
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。