Slower but easy to understand C++ code using BFS.


  • 0
    P

    Find all cells with 'O' at the border of the map.
    Fill all paths from them with "#".
    The remaining 'O' not filled by '#' are islands.

    #include <queue>
    using namespace std;
    
    class Solution {
    public:
        int n_rows;
        int n_cols;
        int last_row;
        int last_col;
    
        inline void fill(vector<vector<char>>& board, int row, int col) {
            // BFS
            queue<pair<int, int>> q;
            board[row][col] = '#'; // mark the cell infeasible
            q.push(make_pair(row, col));
            while(!q.empty()) {
                auto pos = q.front();
                q.pop();
                row = pos.first;
                col = pos.second;
                if(row > 0 && board[row - 1][col] == 'O') {
                    board[row - 1][col] = '#';
                    q.push(make_pair(row - 1, col));
                }
                if(row < last_row && board[row + 1][col] == 'O') {
                    board[row + 1][col] = '#';
                    q.push(make_pair(row + 1, col));
                }
                if(col > 0 && board[row][col - 1] == 'O') {
                    board[row][col - 1] = '#';
                    q.push(make_pair(row, col - 1));
                }
                if(col < last_col && board[row][col + 1] == 'O') {
                    board[row][col + 1] = '#';
                    q.push(make_pair(row, col + 1));
                }
            }
        }
    
        void solve(vector<vector<char>>& board) {
            n_rows = board.size();
            if(!n_rows)
                return;
            n_cols = board[0].size();
            if(!n_cols)
                return;
    
            last_row = n_rows - 1;
            last_col = n_cols - 1;
            // fill all infeasible cells
            for(int row = 0; row < n_rows; ++row) {
                if(board[row][0] == 'O')
                    fill(board, row, 0);
                if(last_col > 0 && board[row][last_col] == 'O')
                    fill(board, row, last_col);
            }
            for(int col = 0; col < n_cols; ++col) {
                if(board[0][col] == 'O')
                    fill(board, 0, col);
                if(last_row > 0 && board[last_row][col] == 'O')
                    fill(board, last_row, col);
            }
    
            // replace all # with O, and replace all O with X
            for(int row = 0; row < n_rows; ++row) {
                for(int col = 0; col < n_cols; ++col) {
                    if(board[row][col] == 'O')
                        board[row][col] = 'X';
                    else if(board[row][col] == '#')
                        board[row][col] = 'O';
                }
            }
        }
    };
    

Log in to reply
 

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