AM 1189. Minesweeper

Code(Language:C++) (Judger:cloudjudge-cluster-7)

BFS iterationclass Solution {
public:
    /**
     * @param board: a board
     * @param click: the position
     * @return: the new board
     */
    const vector<int> dx = {-1, 1, 0, 0, -1, -1, 1, 1};
    const vector<int> dy = {0, 0, -1, 1, -1, 1, -1, 1}; 
    const int dir = 8; 
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        // Write your code here
        const int m = board.size();
        if(m == 0){
            return board; 
        }
        const int n = board[0].size(); 
        // 'M'
        // use BFS 
        std::queue<vector<int>> q;
        q.push(click); 
        while(!q.empty()){
            click = q.front();
            q.pop();
            
            if(board[click[0]][click[1]] == 'M'){
                board[click[0]][click[1]] = 'X';
                return board; 
            }
            else{
                int cnt = 0; 
                vector<vector<int>> neighbors;
                for(int i = 0; i < dir; i++){
                    int newX = click[0] + dx[i];
                    int newY = click[1] + dy[i]; 
                    if(newX < 0 || newX >= m || newY < 0 || newY >= n){
                        continue; 
                    }
                    if(board[newX][newY] == 'M'){
                        cnt++; 
                    }
                    if(board[newX][newY] == 'E'){
                        neighbors.push_back(vector<int>({newX, newY})); 
                        
                    }
                }
                // has M in neighbors
                if(cnt > 0){
                    board[click[0]][click[1]] = '0' + cnt; 
                }
                else{//no M in neighbors
                    board[click[0]][click[1]] = 'B'; 
                    for(auto nei : neighbors){
                        board[nei[0]][nei[1]] = 'B'; //放在这里的目的是剪纸啊，就等于已经visited了，不再重复放入queue。
                        q.push(vector<int>(nei)); 
                    }
                }
            }
        }
        return board; 
    }
};

recursion




Code(Language:C++) (Judger:cloudjudge-cluster-4)









class Solution {
public:
    /**
     * @param board: a board
     * @param click: the position
     * @return: the new board
     */
    const vector<int> dx = {-1, 1, 0, 0, -1, -1, 1, 1};
    const vector<int> dy = {0, 0, -1, 1, -1, 1, -1, 1}; 
    const int dir = 8; 
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        // Write your code here
        const int m = board.size();
        if(m == 0){
            return board; 
        }
        const int n = board[0].size(); 
        // 'M'
        if(board[click[0]][click[1]] == 'M'){
            board[click[0]][click[1]] = 'X';
            return board; 
        }
        else{
            int cnt = 0; 
            vector<vector<int>> neighbors;
            for(int i = 0; i < dir; i++){
                int newX = click[0] + dx[i];
                int newY = click[1] + dy[i]; 
                if(newX < 0 || newX >= m || newY < 0 || newY >= n){
                    continue; 
                }
                if(board[newX][newY] == 'M'){
                    cnt++; 
                }
                if(board[newX][newY] == 'E'){
                    neighbors.push_back(vector<int>({newX, newY})); 
                }
            }
            // has M in neighbors
            if(cnt > 0){
                board[click[0]][click[1]] = '0' + cnt; 
            }
            else{//no M in neighbors
                board[click[0]][click[1]] = 'B'; 
                for(auto nei : neighbors){
                    board[nei[0]][nei[1]] = 'B'; 
                    updateBoard(board, nei); 
                }
            }
        }
        return board; 
    }
};