算法实验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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。