529. Minesweeper (M)

Let's play the minesweeper game (Wikipedia, online game)!

You are given an m x n char matrix board representing the game board where:

• 'M' represents an unrevealed mine,

• 'E' represents an unrevealed empty square,

• 'B' represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals),

• digit ('1' to '8') represents how many mines are adjacent to this revealed square, and

• 'X' represents a revealed mine.

You are also given an integer array click where click = [clickr, clickc] represents the next click position among all the unrevealed squares ('M' or 'E').

Return the board after revealing this position according to the following rules:

1. If a mine 'M' is revealed, then the game is over. You should change it to 'X'.

2. If an empty square 'E' with no adjacent mines is revealed, then change it to a revealed blank 'B' and all of its adjacent unrevealed squares should be revealed recursively.

3. If an empty square 'E' with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.

4. Return the board when no more squares will be revealed.

Example 1:

Input: board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0]
Output: [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

Example 2:

Input: board = [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]], click = [1,2]
Output: [["B","1","E","1","B"],["B","1","X","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

Constraints:

• m == board.length

• n == board[i].length

• 1 <= m, n <= 50

• board[i][j] is either 'M', 'E', 'B', or a digit from '1' to '8'.

• click.length == 2

• 0 <= clickr < m

• 0 <= clickc < n

• board[clickr][clickc] is either 'M' or 'E'.

Solution:

非常简单易懂的java BFS, 原则是能用BFS就别用任何递归。 输入判断我没写，实际面试里可以跟面试官确认是否需要

这道题我拆分了三个子函数，是为了满足工业代码需要注意的Cognitive Complexity, 大意就是一个函数体里if和for过多的话，因为得记住现在的判断条件，所以if/for越多越难让他人理解你的代码。因此尽量拆分出子函数（即使功能只有几行），这样逻辑上便于他人理解，而且能通过code quality check （比如sonarlint). Cognitive Complexity拓展阅读

这道题对java不是那么熟练的童鞋来说，正确用java将int转char是略微需要注意的一点。

直接typecasting char count = (char)neighborMineCount 是错误的。int值会被java看做ASCII，转换出来就不是对应的char了。 可以用以下两种转换方式，第二种更符合工业代码风格，typecasting能避免尽量避免。

char count = (char)(neighborMineCount + '0');

char count = Character.forDigit(neighborMineCount, 10)

遇到M就变成X

遇到已经揭开的就continue

只有B（unraveled）来进行判断要不要去队列。根据周围MINE的数量来判断

class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        Queue<int[]> queue  = new LinkedList<int[]>();
        queue.offer(click);
        while(!queue.isEmpty())
        {
            int[] current = queue.poll();
            int currentX = current[0];
            int currentY = current[1];
            char c = board[currentX][currentY];

            if(c == 'M')
            {
                board[currentX][currentY] = 'X';
                continue;
            }
            if(c != 'E')
            {
               // has been revealed e.g. 1 to 8, or Blank B
                continue;
            }

            List<int[]> neighbours = getNeighbours(currentX, currentY, board);
            int mineCount = getMineCount(neighbours, board);
            if(mineCount == 0)
            {
               board[currentX][currentY] = 'B';
               for(int[] neighbor: neighbours)
               {
                   queue.offer(neighbor);
               }
            }
            else
            {
                board[currentX][currentY] = (char) (mineCount + '0');
            }

        }
        return board;

    }

    public List<int[]> getNeighbours(int x, int y, char[][] board)
    {
       List<int[]> neighbors = new ArrayList<>();
       int[] directX = {-1,-1,-1,0,0,1,1,1};
       int[] directY = {-1,0,1,-1,1,-1,0,1};
       for(int i = 0; i< 8; i++)
       {
           int nextX = x+directX[i];
           int nextY = y+directY[i];
           if(nextX <0 || nextX >=board.length || nextY < 0 || nextY >= board[0].length)
           {
               continue;
           }
           neighbors.add(new int[]{nextX, nextY});
       }
      return neighbors;
    }

    public int getMineCount(List<int[]> neighbors ,char[][] board)
    {
        int count = 0;
        for(int[] n: neighbors)
        {
            if(board[n[0]][n[1]] == 'M' || board[n[0]][n[1]] == 'X')
            {
                count ++;
            }
        }
        return count;

    }
}