C++ 12ms DFS AC solution


  • 0
    M
    class Solution {
    public:
        vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
            if(board[click[0]][click[1]] == 'M'){
                board[click[0]][click[1]] = 'X';
                return board;
            }
            
            m = board.size(), n = board[0].size();
            dfs(board, click[0], click[1]);
            return board;
        }
        
    private:
        int m, n;
        const vector<vector<int>> dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        void dfs(vector<vector<char>>& board, int x, int y){
            if(x < 0 || x >= m || y < 0 || y >= n) return;
            
            if(board[x][y] == 'E'){
                int cnt = 0;
                for(auto dir : dirs){
                    int r = x + dir[0], c = y + dir[1];
                    if(r >= 0 && r < m && c >= 0 && c < n) 
                        cnt += board[r][c] == 'M';
                }
                if(cnt)
                    board[x][y] = cnt + '0';
                else{
                    board[x][y] = 'B';
                    for(auto dir : dirs) 
                        dfs(board, x + dir[0], y + dir[1]);
                }
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.