题解 | #D. 小红的扫雷游戏#

欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏

D. 小红的扫雷游戏

一开始想着，是否可以搞一个方程组

如果确定为雷和非雷，这些是可解的，还有一些不能明确解的。

然后想想，这我也不会呀，重新审视了下数据范围，4*4，还有雷/非雷, 这个0-1特性，所以想到了全枚举状态，然后进行验证。

如果一个合法的状态，可以对相应的格子进行打标签。

如果一个格子，即被标签为雷，又被打标签为非雷，那就是不确定，反之就是确定态。

在来分析下时间复杂度为, O(2^16 * 16 * 8), 这是理论上复杂度，实际上因为游戏本身的限制，并没有这个高。

写出来，还是挺有意思的，这个题目。

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    static int[][] dirs = new int[][] {
            {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}
    };

    static boolean verify(char[][] chess, int s) {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                char c = chess[i][j];
                if (c == '.') continue;
                int p = c - '0';
                int mine = 0;
                for (int t = 0; t < dirs.length; t++) {
                    int y0 = i + dirs[t][0];
                    int x0 = j + dirs[t][1];
                    if (y0 >= 0 && y0 < 4 && x0 >= 0 && x0 < 4) {
                        int ts = y0 * 4 + x0;
                        if ((s & (1 << ts)) != 0) {
                            mine++;
                        }
                    }
                }
                if (mine != p) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        char[][] chess = new char[4][];

        int notMine = (1 << 16) - 1;
        for (int i = 0; i < 4; i++) {
            chess[i] = sc.next().toCharArray();
            for (int j = 0; j < 4; j++) {
                if (chess[i][j] != '.') {
                    notMine -= 1 << (i * 4 + j);
                }
            }
        }

        // 收藏可能解, 1(0b01)一定是非雷，2(0b10)一定雷，3(0b11)则不确定
        int[][] vis = new int[4][4];

        // 枚举所有的可能性, 因为只有2^16种可能
        int range = 1 << 16;
        for (int i = 0; i < range; i++) {
            if ((i | notMine) == notMine && verify(chess, i)) {
                for (int r = 0; r < 4; r++) {
                    for (int c = 0; c < 4; c++) {
                        if ((i & (1 << (4 * r + c))) == 0) {
                            vis[r][c] |= 1;
                        } else {
                            vis[r][c] |= 2;
                        }
                    }
                }
            }
        }

        // 地雷图还原
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (chess[i][j] == '.') {
                    if (vis[i][j] == 1) chess[i][j] = 'O';
                    else if (vis[i][j] == 2) chess[i][j] = 'X';
                }
            }
        }

        for (int i = 0; i < 4; i++) {
            System.out.println(new String(chess[i]));
        }
    }

}