Clean and understanable DFS C++ Solution with comments


  • 0
    T

    Three steps to solve the problem:
    Step 1: mark all the border '0' and its neighbors to '#'
    Step 2: Convert all the remaining '0' to 'X'
    Step 3: Convert all the '#' back to '0'

    Here are the clean and concise implementation (without lots of guards which reduce the readability).

    class Solution {
    public:
        void mark(vector<vector<char>>& board, int i, int j) {
            if (i < 0 || i >= R || j < 0 || j >= C || board[i][j] == 'X' || board[i][j] == '#')
                return;
        
            board[i][j] = '#';
            mark(board, i - 1, j);
            mark(board, i + 1, j);
            mark(board, i, j - 1);
            mark(board, i, j + 1);
        }
        
        void solve(vector<vector<char>>& board) {
            if (board.empty())
                return;
            
            R = board.size();
            C = board[0].size();
            
            // Step 1: mark all the border '0' and its neighbors to '#'
            for (int i = 0; i < R; i++) {
                mark(board, i, 0); // first column
                mark(board, i, C - 1); // last column
            }
            
            for (int j = 1; j < C - 1; j++) {
                mark(board, 0, j); // first row
                mark(board, R - 1, j); // last row
            }
            
            // Step 2: Convert all the remaining '0' to 'X'
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (board[i][j] == 'O')
                        board[i][j] = 'X';
                }
            }
            
            // Step 3: Convert all the '#' back to '0'
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (board[i][j] == '#')
                        board[i][j] = 'O';
                }
            }
        }
    
    private:
        int R;
        int C;
    };
    

    This is an improved version of this one, thanks to the author:

    https://leetcode.com/problems/surrounded-regions/discuss/41612


Log in to reply
 

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