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

• 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;
}
``````

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