C++ BFS Solution, Well Factored, Easy to Understand


  • 0
    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';
            else {
                queue<vector<int>> q({click});
                while(q.size()) { // BFS
                    vector<int> pos = q.front(); q.pop();
                    int res = checkMines(board, pos);
                    board[pos[0]][pos[1]]=res?'0'+res:'B';
                    for(auto it:getNeighbors(board,pos))
                        if(!res&&board[it[0]][it[1]]=='E') { // res check should be promoted before for loop, here just to eliminate one line
                            q.push(it);
                            board[it[0]][it[1]]='V'; // change to 'V' means visited
                        }
                }
            }
            return board;
        }
        bool checkBoundary(vector<vector<char>>& board, int x, int y) {
            if(x>=0&&x<board.size()&&y>=0&&y<board[0].size())
                return true;
            return false;
        }
        int checkMines(vector<vector<char>>& board, vector<int>& pos) {
            int sum=0;
            for(int i=-1;i<=1;i++)
                for(int j=-1;j<=1;j++)
                    if((i!=0||j!=0)&&checkBoundary(board,pos[0]+i,pos[1]+j)&&board[pos[0]+i][pos[1]+j]=='M')
                        sum++;
            return sum;
        }
        vector<vector<int>> getNeighbors(vector<vector<char>>& board, vector<int>& pos) {
            vector<vector<int>> res;
            for(int i=-1;i<=1;i++)
                for(int j=-1;j<=1;j++)
                    if((i!=0||j!=0)&&checkBoundary(board,pos[0]+i,pos[1]+j))
                        res.push_back(vector<int>({pos[0]+i,pos[1]+j}));
            return res;
        }
    };
    

Log in to reply
 

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