529. 扫雷游戏

题目:https://leetcode-cn.com/problems/minesweeper/

代码:

class Solution {

    /**
     * 1如果一个地雷('M')被挖出,游戏就结束了- 把它改为 'X'。
     * 2如果一个没有相邻地雷的空方块('E')被挖出,修改它为('B'),并且所有和其相邻的未挖出方块都应该被递归地揭露。
     * 3如果一个至少与一个地雷相邻的空方块('E')被挖出,修改它为数字('1'到'8'),表示相邻地雷的数量。
     * 4如果在此次点击中,若无更多方块可被揭露,则返回面板。
     * @param board
     * @param click
     * @return
     */
    public char[][] updateBoard(char[][] board, int[] click) {
        //打印,方便调试看过程,提交时去掉
//        this.printBoard(board, click);

        int i = click[0];
        int j = click[1];
        //考虑该方法会递归调用,所以以下逻辑仅在click点没有点击过的情况下执行
        if (board[i][j] != 'E' && board[i][j] != 'M') {
            return board;
        }
        //1如果一个地雷('M')被挖出,游戏就结束了- 把它改为 'X'。
        if (board[i][j] == 'M') {
            board[i][j] = 'X';
            return board;
        }
        //获取click点四周地雷数量
        int countM =this.countM(board, click);
        if (countM == 0) {
            //2如果一个没有相邻地雷的空方块('E')被挖出,修改它为('B'),并且所有和其相邻的未挖出方块都应该被递归地揭露。
            board[i][j] = 'B';
            //递归点击周围坐标
            int[][] roundPos = this.roundPos(board, click,false);
            for (int p = 0; p < roundPos.length; p++) {
                board = this.updateBoard(board, roundPos[p]);
            }
        }else{
            //3如果一个至少与一个地雷相邻的空方块('E')被挖出,修改它为数字('1'到'8'),表示相邻地雷的数量。
            board[i][j] = (char) ('0'+countM);
        }
        //4如果在此次点击中,若无更多方块可被揭露,则返回面板。
        return board;
    }

    /**
     * 获取click位置四周有几个地雷
     * @param board
     * @param click
     * @return
     */
    public int countM(char[][] board, int[] click){
        int count = 0;
        int[][] roundPos = this.roundPos(board, click,true);
        for (int p = 0; p < roundPos.length; p++) {
            int i = roundPos[p][0];
            int j = roundPos[p][1];
            if (board[i][j] == 'M') {
                count++;
            }
        }
        return count;
    }

    /**
     * 获取click点四周的坐标
     * @param board
     * @param click
     * @param all 为true时返回所有坐标,false返回未点击的坐标
     * @return
     */
    public int[][] roundPos(char[][] board, int[] click, boolean all) {
        int i = click[0];
        int j = click[1];
        //计算需要遍历的区域范围(click的四周,考虑边界问题)
        int iStart = Math.max(0, i - 1);
        int iEnd = Math.min(board.length-1, i + 1);
        int jStart = Math.max(0, j - 1);
        int jEnd = Math.min(board[i].length-1, j + 1);
        //坐标数组
        int [][] pos = new int[8][2];
        int size = 0;
        //遍历click四周的点,获取坐标
        for (int ii = iStart; ii <= iEnd; ii++) {
            for (int jj = jStart; jj <= jEnd; jj++) {
                if (ii == i && jj == j) {
                    //click的位置,跳过
                    continue;
                }
                //根据all参数判断全部添加还是只添加未点击过的点
                if (all || board[ii][jj] == 'E') {
                    pos[size][0] = ii;
                    pos[size][1] = jj;
                    size++;
                }
            }
        }
        //根据size截取pos数组
        int[][] finalPos = new int[size][2];
        for (int s = 0; s < size; s++) {
            finalPos[s] = pos[s];
        }
        return finalPos;
    }

    /**
     * 打印
     * @param board
     */
    public void printBoard(char[][] board, int[] click) {
        int ci = -1;
        int cj = -1;
        if (click != null) {
            ci = click[0];
            cj = click[1];
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (i == ci && j == cj) {
                    //标记点击点
                    System.out.print("["+board[i][j]+"]");
                }else{
                    //普通点
                    System.out.print(" "+board[i][j] + " ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

}

测试代码:

public class Test {

    public static void main(String[] args) {

        char[][] board = new char[][]{
                {'E', 'E', 'E', 'E', 'E'},
                {'E', 'E', 'M', 'E', 'E'},
                {'E', 'E', 'E', 'E', 'E'},
                {'E', 'E', 'E', 'E', 'E'}
        };
        int[] click = new int[]{3, 0};

        Solution s = new Solution();
        char[][] chars = s.updateBoard(board, click);
        s.printBoard(chars, null);
    }

}

看到题目的第一眼,我是懵逼的。这题目规则有点复杂,算了,我还是先来2盘扫雷回忆回忆。http://www.saolei.org.cn/

言归正传,虽然题目有点复杂,但是仔细梳理之后要点就一下几个:
0、题目给定一个二维数组做扫雷面板(棋盘),一个一维数组做挖雷点(下棋)。
1、如果一个地雷(’M’)被挖出,游戏就结束了- 把它改为 ‘X’。
2、如果一个没有相邻地雷的空方块(’E’)被挖出,修改它为(’B’),并且所有和其相邻的未挖出方块都应该被递归地揭露。
3、如果一个至少与一个地雷相邻的空方块(’E’)被挖出,修改它为数字(’1’到’8’),表示相邻地雷的数量。
4、如果在此次点击中,若无更多方块可被揭露,则返回面板。

为了方便调试,我增加了一个打印面板的方法,用于打印过程以及点击点(辅助的方法,提交时注意注释掉)。结合需求,我认为需要有如下几个方法:
1、通过点击点获取点击点四周坐标,方法roundPos。这个方法需要注意的要点就是防止越界,以及需要考虑根据参数判断是获取四周所有点还是仅获取四周未点击过的点。(比较困难的方法)
2、通过点击点获取点击点四周地雷数量,方法countM。有了1提供的方法,本方法实现变得简单的多。
3、游戏方法updateBoard。按照游戏规则进行对应的判断及操作即可。需要注意的是如果匹配上游戏规则2,即挖到的点是B的情况下,要递归调用本方法点击其四周未点击过的点。
4、没了,请参考上方具体代码及注释。

总结:经过提交之后的结果参考。虽然题目解开了,但是效率上有点惨不忍睹,不过我觉得当前这个方法应该算相对比较好理解的。