---
# System prepended metadata

title: 0529. Minesweeper
tags: [Leetcode, BFS, FaceBook, DFS, Medium]

---

# 0529. Minesweeper
###### tags: `Leetcode` `Medium` `FaceBook` `DFS` `BFS`
Link: https://hackmd.io/pnoapkn9Teua5aUxxUemSw
## 思路
分情况考虑
如果click的地方是M,变成X之后return
如果click的地方附近有mine,变成mine数之后return
如果click的地方附近没有雷,DFS
## Code
```java=
class Solution {
    int[][] directions = new int[][]{{-1,1},{-1,0},{-1,-1},{0,-1},{0,1},{1,1},{1,0},{1,-1}};
    public char[][] updateBoard(char[][] board, int[] click) {
        int x = click[0], y = click[1];
        if(board[x][y]=='M'){
            board[x][y]='X';
            return board;
        }
        int countMine = checkMine(board, click);
        if(countMine!=0){
            board[x][y]=(char)(countMine+'0');
            return board;
        }
        else{
            Stack<int[]> stack = new Stack<>();
            stack.add(click);
            while(!stack.isEmpty()){
                int[] curr = stack.pop();
                if(board[curr[0]][curr[1]]=='B'||Character.isDigit(board[curr[0]][curr[1]])) continue;
                int count = checkMine(board, curr);
                if(count == 0){
                    board[curr[0]][curr[1]]='B';
                    stack.addAll(getNext(board, curr));
                }
                else{
                    board[curr[0]][curr[1]]=(char)(count+'0');
                }
            }
            return board;
        }
    }
    private List<int[]> getNext(char[][] board, int[] pos){
        List<int[]> ans = new ArrayList<>();
        for(int i = 0;i < directions.length;i++){
            int newX = pos[0]+directions[i][0];
            int newY = pos[1]+directions[i][1];
            if(newX>=0 && newX<board.length && newY>=0 && newY<board[0].length){
                ans.add(new int[]{newX, newY});
            }
        }
        return ans;
    }
    
    private int checkMine(char[][] board, int[] pos){
        int count = 0;
        for(int i = 0;i < directions.length;i++){
            int newX = pos[0]+directions[i][0];
            int newY = pos[1]+directions[i][1];
            if(newX>=0 && newX<board.length && newY>=0 && newY<board[0].length && board[newX][newY]=='M'){
                count+=1;
            }
        }
        return count;
    }
}
```