C++ BFS with Little Explanation


  • 0
    L
        vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
            if (board.empty()) return board;
            int m = board.size(), n = board[0].size();
            
            // Eight adjacent points
            // (-1, -1)  (-1, 0)  (-1, 1)
            // ( 0, -1)  (curr)   ( 0, 1)
            // ( 1, -1)  ( 1, 0)  ( 1, 1)
            vector<vector<int>> dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
            queue<pair<int, int>> q;
            if (board[click[0]][click[1]] != 'M')
                q.emplace(click[0], click[1]);
            else
                board[click[0]][click[1]] = 'X';
            
            while (!q.empty()) {
                auto cur = q.front(); q.pop();
                int mines = 0;
                vector<pair<int, int>> tmp;
                // ignore already handled point
                if (board[cur.first][cur.second] != 'E') continue;
    
                // traverse eight adjacent points to find mines
                for (auto d : dirs) {
                    int x = cur.first + d[0];
                    int y = cur.second + d[1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        if (board[x][y] == 'M')
                            mines++;
                        tmp.emplace_back(x, y);
                    }
                }
                if (mines) {
                    board[cur.first][cur.second] = '0' + mines;
                } else {
                    board[cur.first][cur.second] = 'B';
                    // No mine, then save eight adjacent points for next iteration
                    for (auto elem : tmp) {
                        q.emplace(elem);
                    }
                }
            }
            
            return board;
        }
    

Log in to reply
 

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