算法实验T3——POJ1753 Flip Game
2023-12-28 22:46:40
题目大意:
????????有 4*4 的正方形,每个格子要么是黑色,要么是白色,当把一个格子的颜色改变(黑 ->? 白或者白 -> 黑)时,其周围上下左右(如果存在的话)的格子的颜色也被反转,问至少反转几个格子可以使 4 * 4 的正方形变为纯白或者纯黑?
思路:
????????首先我们发现主动翻转格子的结果和顺序无关,因为交换翻转顺序后,全局所有格子的翻转次数(包括主动和被动)都不会变,因此最终状态也不会变。这个性质说明对于最终解,我们只关心16个格子每个主动翻转几次,而不需关心先后,因此我们可以独立考察每一格。可以发现,对于每一个格子,其实只有主动翻转一次和不主动翻转两种情况,因为主动翻转两次效果会完全抵消。这样,最多整体上翻转16次,一共2^16 = 65536种情况,完全可以暴力枚举。因为是求最少步数,我们可以从0次到16次枚举,对于每一种主动翻转次数,枚举出所有情况,对每一种情况模拟构造检查是否是解,如果是,则当前主动翻转次数就是最终解。
AC代码:
#include<iostream>
#include<cstdio>
char map[4][4];
using std::cin;
void read() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cin >> map[i][j];
}
}
}
bool simul(int* arr, int size_arr) {// simul()用来模拟检查是否是解,arr中存储哪些格子要翻转
int x, y;
int dire[4][2] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
char tmp_map[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
tmp_map[i][j] = map[i][j];
}
}
for (int i = 0; i < size_arr; i++) {
x = arr[i] / 4;
y = arr[i] % 4;
if (tmp_map[x][y] == 'w') {
tmp_map[x][y] = 'b';
}
else {
tmp_map[x][y] = 'w';
}
for (int j = 0; j < 4; j++) {
int newx = x + dire[j][0];
int newy = y + dire[j][1];
if (newx < 0 || newy < 0 || newx >= 4 || newy >= 4)
continue;
if (tmp_map[newx][newy] == 'w') {
tmp_map[newx][newy] = 'b';
}
else {
tmp_map[newx][newy] = 'w';
}
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (tmp_map[i][j] != tmp_map[0][0]) {
return false;
}
}
}
return true;
}
bool check(int num, int count, int* arr) {
if (count == num) {
return simul(arr, num);
}
for (int i = (count == 0 ? 0 : arr[count - 1] + 1) ; i < 16 - (num - count) + 1; i++) {
arr[count] = i;
if (check(num, count + 1, arr))
return true;
}//枚举总共主动翻转num次的所有情况,arr用于存储要翻转的格子。
return false;
}
int get_min() {
int arr[16];
for (int i = 0; i <= 16; i++) {//从小到大枚举每一种主动翻转次数
if (check(i, 0, arr)) {
return i;
}
}
return -1;
}
int main() {
read();
int res = get_min();
if (res != -1) printf("%d", res);
else printf("Impossible");
return 0;
}
文章来源:https://blog.csdn.net/qq_43010742/article/details/135212607
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!