关于网站开发的毕业设计,电子商务网站开发实例,推广案例,福州网站建设金森POJ-3279. Fliptile#xff08;递推搜索#xff09;
Vjudge链接
题目描述
农场主约翰知道#xff0c;一头智力得到满足的奶牛是一头快乐的奶牛#xff0c;它会产更多的奶。他为奶牛安排了一项脑力活动#xff0c;让它们摆弄一个 M N M N MN 的方格 ( 1 ≤ M ≤ 15 …POJ-3279. Fliptile递推搜索
Vjudge链接
题目描述
农场主约翰知道一头智力得到满足的奶牛是一头快乐的奶牛它会产更多的奶。他为奶牛安排了一项脑力活动让它们摆弄一个 M × N M × N M×N 的方格 ( 1 ≤ M ≤ 15 ; 1 ≤ N ≤ 15 ) (1 ≤ M ≤ 15;1 ≤ N ≤ 15) (1≤M≤15;1≤N≤15)每个方格的一面是黑色的另一面是白色的。
正如人们所猜测的那样当翻转一块白色瓷砖时它就会变成黑色当翻转一块黑色瓷砖时它就会变成白色。当奶牛翻转瓷砖使每块瓷砖的白色面朝上时它们就会得到奖励。不过奶牛的蹄子比较大当它们试图翻转某块瓷砖时也会翻转所有相邻的瓷砖与被翻转瓷砖共用一条完整边缘的瓷砖。由于翻转很累奶牛们希望尽量减少翻转的次数。
帮助奶牛确定所需的最少翻转次数以及为达到最少翻转次数而需要翻转的位置。如果有多种方法都能以最少的翻转次数完成任务则在输出中以字符串形式返回词序最少的一种方法。如果任务不可能完成则打印一行并注明 “IMPOSSIBLE”。
输入
第 1 1 1 行 两个空格分隔的整数 M M M 和 N N N
第 2... M 1 2...M1 2...M1 行 第 i 1 i1 i1 行描述网格第 i i i 行的颜色从左到右用 N N N 个空格分隔的整数表示 1 1 1 表示黑色 0 0 0 表示白色
输出
第 1... M 1...M 1...M 行每行包含 N N N 个空格分隔的整数每个整数指定特定位置的翻转次数。
样例输入
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1样例输出
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0题意
给定一个 01 01 01 矩阵可以任意选择翻转一个点使得 0 0 0 变成 1 1 1 1 1 1 变成 0 0 0 并且该点上下左右的四个点会按照同样的规律进行翻转现在问最少需要翻转多少次可以使得整个矩阵都是 0 0 0 如果有多种方式请输出字典序最小的一种若无法达到则输出 “impossible”。
思路
首先一个点翻转两次及以上是没有意义的。因为翻转两次等于不反转翻转奇数次等于翻转一次所以我们只需要考虑翻转一次的情况。
那么每个点只有翻与不翻两种情况直接枚举的话 n ∗ ( 2 n ) n*(2^n) n∗(2n) 会超时所以需要优化枚举方式。
这里设翻转某个点 (i, j) 的操作为 turn(x, y) 如果逐个枚举的话当翻转当前点的时候会使上一行也翻转从而破坏上一行的状态所以只能用下一行去改变上一行的状态。
并且操作的顺序也不会影响最终的结果。那么若当前行某一点 (i, j) 的状态为 1 那就可以用所在列的下一行 (i 1, j) 去执行 turn 操作使得 (i, j) 的状态变为 0 。
综上我们可以先确定第一行的操作方案枚举第一行所有的操作再依此递推后面行数的情况最后判断最后一行的状态是否全部变成了 0 即可。
同时我们使用二进制枚举第一行的话还可以保证是按字典序来枚举的也符合题目要求。
代码
#include iostream
#include cstdio
#include cstring
#include algorithm
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false), cin.tie(0);using namespace std;
const int N 20;// 翻转数字上下左右,1-0,0-1,需要将所有的数都变成0
int n, m;
int g[N][N], backup[N][N]; // 原数组备份数组(备份数组用来恢复原来的状态)
int temp[N][N]; // 临时状态数组(保存每次枚举时当前数组的状态)
int ans[N][N]; // 答案数组
int dx[] {0, -1, 0, 1, 0};
int dy[] {0, 0, 1, 0, -1};
int res;// 转换瓷砖状态
void turn(int x, int y)
{for (int i 0; i 5; i){int xx x dx[i], yy y dy[i];if (xx 0 xx n yy 0 yy m){g[xx][yy] ^ 1; // 异或,变成相反数// if (g[xx][yy] 1) g[xx][yy] 0;// else g[xx][yy] 1;}}temp[x][y] 1;
}void work()
{//先枚举第一行的所有情况使用二进制枚举一共2^m种for (int k 0; k 1 m; k){int cnt 0;memcpy(backup, g, sizeof g); //备份原数组memset(temp, 0, sizeof temp); //每次都需要初始化临时数组// 对第1行处理for (int j 0; j m; j)if (k j 1){cnt;turn(0, j);}// 逐个枚举第2~n-1行for (int i 0; i n - 1; i)for (int j 0; j m; j)if (g[i][j] 1){cnt;turn(i 1, j); // 对下一行处理}bool flag true;for (int j 0; j m; j) // 判断最后一行是否合法if (g[n - 1][j] 1){flag false;break;}// 判断最小操作次数if (flag cnt res){res cnt;memcpy(ans, temp, sizeof temp); // 更新答案数组}// 枚举完一种情况后还原成初始状态memcpy(g, backup, sizeof backup);}
}int main()
{IOS;res INF;cin n m;for (int i 0; i n; i)for (int j 0; j m; j)cin g[i][j];work();if (res INF) cout IMPOSSIBLE endl;else {for (int i 0; i n; i){for (int j 0; j m; j)cout ans[i][j] ;cout endl;}}return 0;
}
