C++ DFS and BFS Solution


  • 0
    K

    Minesweeper Update Board
    In this problem, we are given 2D matirx of characters that represent a board.
    M - Unrevealed mine
    X - Revealed mine
    B - Revealed blank square
    E - Unrevealed Empty square
    D - Revealed square with digit representing the number of mines adjacent to this square

    Now, we need to follow the following rules to update the board when a click is performed
    a.) If an unrevealed mine 'M' is clicked, Change that to 'X' - Game Over!
    b.) If an empty square 'E' is clicked and has NO adjacent mines next to it, change it to a blank square 'B' and recursively reveal all of its adjacent unrevealed squares
    c.) If an empty square 'E' is clicked and has AT LEAST 1 adjacent mine, change it to a digit square 'D' where D = number of adjacent mines
    d.) Return the board when no more squares will be revealed

    DFS Solution:

    class Solution {
    public:
        vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
            int i = click[0] , j = click[1] ;
            // If the click position is an 'M' change to 'X' and return
            if(board[i][j] == 'M'){
                board[i][j] = 'X';
            }
            // This means that the click position is an 'E'. Recursively update the board
            else
                updateRecurse(board, i, j);
            return board;
        }
    private:
            void updateRecurse(vector<vector<char>>& board, int i, int j){
            int num = countAdjacentMines(board, i, j);
            // Set the square to the number of adjacent mines ( if > 0 )
            if(num > 0){
                board[i][j] = (char)(num + '0');
            }
            // Set the square to a revealed blank square 'B' & Recursively update the 8 adjancent squares.
            else{
                board[i][j] = 'B';
                for(int x=i-1; x <= i + 1; x++){
                    for(int y=j-1; y <= j + 1; y++){
                        if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size() || (x == i && y == j) || board[x][y] != 'E')
                            continue;
                        updateRecurse(board, x, y);
                    }
                }
            }
        }
        int countAdjacentMines(vector<vector<char>>& board, int i, int j){
            int count = 0;
            for(int x=i-1; x <= i + 1; x++){
                for(int y=j-1; y <= j +1; y++){
                    if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size() || (x == i && y == j))
                        continue;
                    else if(board[x][y] == 'M'){
                        count++;
                    }
                }
            }
            return count;
        }
    };
    

    BFS Solution:

    class Solution {
    public:
        vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
            // If the click position is an 'M' change to 'X' and return
            if(board[click[0]][click[1]] == 'M'){
                board[click[0]][click[1]] = 'X';
                return board;
            }
            // This means that the click position is an 'E'. 
            queue<vector<int>> q({click});
            while(!q.empty()){
                cout << q.size() << endl;
                int i = q.front()[0], j = q.front()[1];
                int num = countAdjacentMines(board, q.front());
                // Set the square to the number of adjacent mines ( if > 0 ) or mark as blank square
                board[i][j] = num > 0 ? (char)(num + '0') : 'B';
                // Push adjacent, legal , unvisited squares into the queue
                for(int x=i-1; num == 0 && x <= i + 1; x++){
                    for(int y=j-1; y <= j + 1; y++){
                        if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size() || (x == i && y == j) || board[x][y] != 'E')
                            continue;
                        vector<int> adj = {x, y}; 
                        q.push(adj);
                        // Mark as 'V' for now to avoid being pushed into the queue again.. actual value update in a subsequent iter
                        board[x][y] = 'V';
                    }
                }
                // Pop the front
                q.pop();
            }
            return board;
        }
    private:
    
        int countAdjacentMines(vector<vector<char>>& board, vector<int>& click){
            int count = 0, i = click[0], j = click[1];
            for(int x=i-1; x <= i + 1; x++){
                for(int y=j-1; y <= j +1; y++){
                    if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size() || (x == i && y == j))
                        continue;
                    else if(board[x][y] == 'M'){
                        count++;
                    }
                }
            }
            return count;
        }
    };
    

Log in to reply
 

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