暴力枚举+位运算：PIPI的方格

墨蓝 2023-10-06 19:24 44阅读 0赞

## 暴力枚举+位运算：PIPI的方格 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路： ####

首先，若我们考虑在原方格上进行操作，问题将会变得相当复杂。我们需要把构造性问题转化为验证性问题，枚举出所有满足条件的方格，再将这些方格与原方格比较，从而得到最少要进行的操作数

对于枚举出所有方格，若对方格中每个点的情况进行枚举，复杂度太高，显然不合理。需注意到，若第一行已经确定，那么若要使第一行满足条件，我们可以确定第二行的取值，依次类推。 最后需检验最后一行是否满足条件。因此我们只要枚举出第一行的所有情况即可，我们可以把第一行的取值看成一个二进制数，第一行的所有状态即为000…000 ~ 111…111，共有2 ^ n种情况，使用代表每个位置的二进制数（如000…001表示第一列的元素）与状态二进制数进行与运算，即可得到第一行的取值。

**需注意的点** :

*  需要在构造方格的过程中与原方格比较，得到修改次数，而不是在构造完之后遍历比较，这样可以提速，防止时间超限。在构造方格的过程中，若某个点为0，而原来方格中该点为1，则该方案不满足要求，进行下一种情况的枚举

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int[][] table = new int[16][16];
            int[][] readTable = new int[16][16];
            int[][] location = {
        {
        -1, -1}, {
        -1, 1}, {
        -2, 0}};
            int[][] lastColumn = {
        {
        -1, 0}, {
        0, -1}, {
        0, 1}};
            int n, i, j, p, ans, fail;
            int[] change = new int[1];
            while (scanner.hasNextInt()) {
        
                n = scanner.nextInt();
                fail = 0;
                ans = 1000;
                for (i = 0; i < n; i++) {
        
                    for (j = 0; j < n; j++) {
        
                        readTable[i][j] = scanner.nextInt();
                    }
                }
                for (i = 0; i < (1 << n); i++) {
        
                    change[0] = 0;
                    for (j = 0; j < n; j++) {
        
                        if ((i & (1 << j)) != 0) {
        
                            table[0][j] = 1;
                            if (readTable[0][j] == 0) {
        
                                change[0]++;
                            }
                        } else {
        
                            if (readTable[0][j] == 1) {
        
                                fail = 1;
                                break;
                            }
                            table[0][j] = 0;
                        }
                    }
                    if (fail == 1) {
        
                        fail = 0;
                        continue;
                    }
                    for (p = 1; p < n; p++) {
        
                        if (!checkLine(p, location, table, n, readTable, change)) {
        
                            fail = 1;
                            break;
                        }
                    }
                    if (fail == 1) {
        
                        fail = 0;
                        continue;
                    }
                    if (!checkLastLine(lastColumn, table, n)) {
        
                        continue;
                    }
                    if (change[0] < ans) {
        
                        ans = change[0];
                    }
    
                }
                System.out.println(ans == 1000 ? -1 : ans);
            }
        }
    
    
        static boolean checkLine (int line, int[][] location, int[][] table, int n, int[][] readTable, int[] change) {
        
            int j, k, x, y;
            int temp;
            for (j = 0;j < n;j++) {
        
                temp = 0;
                for (k = 0;k < 3;k++) {
        
                    x = line + location[k][0];
                    y = j + location[k][1];
                    if (x >= 0 && x < n && y >= 0 && y < n) {
        
                        temp += table[x][y];
                    }
                }
                if (temp % 2 == 0) {
        
                    if (readTable[line][j] == 1) {
        
                        return false;
                    }
                    table[line][j] = 0;
                } else {
        
                    if (readTable[line][j] == 0) {
        
                        change[0]++;
                    }
                    table[line][j] = 1;
                }
            }
            return true;
        }
    
        static boolean checkLastLine (int[][] lastColumn, int[][] table, int n) {
        
            int j, temp, k, x, y;
            for (j = 0; j < n; j++) {
        
                temp = 0;
                for (k = 0; k < 3; k++) {
        
                    x = n - 1 + lastColumn[k][0];
                    y = j + lastColumn[k][1];
                    if (x >= 0 && x < n && y >= 0 && y < n) {
        
                        temp += table[x][y];
                    }
                }
                if (temp % 2 != 0) {
        
                    return false;
                }
            }
            return true;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/de1b9f8744dd4713b5adeaccd40261e6.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/b9c8c57bec4843ca8fe28b39ddb02838.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/3d7a2ed41b0343b0879f0344a3e02e6e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/00b20ba1b27d41d4853595825d8bb217.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16