DFS, BFS, Union-Find, One-Pass solutions in C++


  • 1
    G

    DFS:

        void helper(vector<vector<char>>& board, int y, int x) {
            int m = (int)board.size(), n = m ? (int)board[0].size() : 0;
            if (y < 0 || x < 0 || y == m || x == n || board[y][x] != 'X')
                return;
            int t[] = {1, 0, -1, 0, 1};
            board[y][x] = '.';
            for (int i = 1; i <= 4; ++i)
                helper(board, y + t[i - 1], x + t[i]);
        }
        int dfs(vector<vector<char>> board) {
            int m = (int)board.size(), n = m ? (int)board[0].size() : 0;
            int count = 0;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (board[i][j] == '.') continue;
                    ++count;
                    helper(board, i, j);
                }
            }
            return count;
        }
    

    BFS:

        int bfs(vector<vector<char>> board) {
            int m = (int)board.size(), n = m ? (int)board[0].size() : 0;
            int t[] = {1, 0, -1, 0, 1}, count = 0;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (board[i][j] == '.') continue;
                    queue<pair<int, int>> q;
                    ++count;
                    q.push({i, j});
                    while (!q.empty()) {
                        auto p = q.front();
                        q.pop();
                        board[p.first][p.second] = '.';
                        for (int k = 1; k <= 4; ++k) {
                            int ii = p.first + t[k - 1], jj = p.second + t[k];
                            if (ii != -1 && ii != m && jj != -1 && jj != n && board[ii][jj] == 'X')
                                q.push({ii, jj});
                        }
                    }
                }
            }
            return count;
        }
    

    Union-Find:

        int ufs(vector<vector<char>>& board) {
            int m = (int)board.size(), n = m ? (int)board[0].size() : 0;
            if (n == 0) return 0;
            int parents[m * n] = {0}, rank[m * n] = {0}, count = 0;
            for (int i = m * n - 1; i >= 0; --i) {
                parents[i] = i;
                rank[i] = 1;
            }
            
            auto find = [&](int a) {
                while (parents[a] != a)
                    a = parents[a] = parents[parents[a]];
                return a;
            };
                
            auto uni = [&](int a, int b) {
                int r1 = find(a), r2 = find(b);
                if (rank[r1] > rank[r2])
                    parents[r2] = r1;
                else
                    parents[r1] = r2, rank[r2] += rank[r1] == rank[r2];
            };
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (board[i][j] == '.') continue;
                    if (j > 0 && board[i][j - 1] == 'X') uni(i * n + j, i * n + j - 1);
                    if (i > 0 && board[i - 1][j] == 'X') uni(i * n + j, (i - 1) * n + j);
                }
            }
            int count = 0;
            for (int i = m * n - 1; i >= 0; --i)
                count += board[i / n][i % n] == 'X' && parents[i] == i;
            return count;
        }
    

    One-pass:

        int one_pass(vector<vector<char>>& board) {
            int m = (int)board.size(), n = m ? (int)board[0].size() : 0, count = 0;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (board[i][j] == '.') continue;
                    count += (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.');
                }
            }
            return count;
        }
    

Log in to reply
 

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