[C++] My easy to understand DFS solution.


  • 0
    J

    Just imagine you are searching in a maze. You can go from the exits, slash all the Os, then mark all the remaining Os as Xs, and revive the dead Os (%). :p

    class Solution {
    private:
        struct Point {
            int x;
            int y;
            Point(int x_, int y_) : x(x_), y(y_) {}
        };
    public:
        void solve(vector<vector<char>> &board) {
            vector<Point> path;
            for (int i = 0; i < board.size(); i++) {
                for (int j = 0; j < board[i].size(); j++) {
                    // only deal with the border
                    if ((j != 0 && j != board[i].size() - 1) &&
                            (i != 0 && i != board.size() - 1)) {
                        continue;
                    }
                    if (board[i][j] != 'O') continue;
                    // find all the Os
                    board[i][j] = '%';  // Slash it.
                    path.push_back(Point(i, j));
                    while (!path.empty()) {
                        Point p = path.back();
                        path.pop_back();
                        if (p.x + 1 < board.size() && board[p.x+1][p.y] == 'O') {
                            board[p.x+1][p.y] = '%';
                            path.push_back(Point(p.x+1, p.y));  // down
                        }
                        if (p.y + 1 < board[p.x].size() && board[p.x][p.y+1] == 'O') {
                            board[p.x][p.y+1] = '%';
                            path.push_back(Point(p.x, p.y+1));  // right
                        }
                        if (p.x > 0 && board[p.x-1][p.y] == 'O') {
                            board[p.x-1][p.y] = '%';
                            path.push_back(Point(p.x-1, p.y));  // up
                        }
                        if (p.y > 0 && board[p.x][p.y-1] == 'O') {
                            board[p.x][p.y-1] = '%';
                            path.push_back(Point(p.x, p.y-1));  // left
                        }
                    }
                }
            }
            for (int i = 0; i < board.size(); i++) {
                for (int j = 0; j < board[i].size(); j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    } else if (board[i][j] == '%') {
                        board[i][j] = 'O';  // Welcome back.
                    }
                }
            }
        }
    };

  • 0
    N

    It looks like a BFS.


  • 0
    J

    ;-) Yes, the essential difference between DFS and BFS is whether you push and pop on the same side.


Log in to reply
 

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