Practice › Graphs
Surrounded Regions
Medium · Graphs · Asked at Amazon, Google, Microsoft, Bloomberg
The board contains X and O. Capture every region of O (connected up/down/left/right) that is completely surrounded by X, by flipping those Os to X. Regions touching the border are not captured. Print the board.
Input
First line: r c. Next r lines: strings of X and O.
Output
The board after capturing, r lines.
Constraints
- 1 ≤ r, c ≤ 200
Instead of finding surrounded regions, find the safe ones: DFS/BFS from every border O and mark them. Flip every unmarked O.
Example 1
Input
4 4 XXXX XOOX XXOX XOXX
Output
XXXX XXXX XXXX XOXX
Example 2
Input
1 1 X
Output
X
Hints
- An O region survives exactly when it touches the border.
- Start a BFS/DFS from every O on the border and mark everything reachable as safe. Every other O gets flipped.
Approach
Push all border O cells into a queue and mark them safe, then flood through adjacent O cells. Afterwards, any O that is not marked safe cannot reach the border — it is surrounded — so turn it into X. This inverts the problem and visits each cell at most once.
Complexity: O(r · c) time · O(r · c) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int R, C;
cin >> R >> C;
vector<string> g(R);
for (auto &row : g) cin >> row;
vector<vector<bool>> safe(R, vector<bool>(C, false));
queue<pair<int, int>> q;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if ((i == 0 || j == 0 || i == R - 1 || j == C - 1) && g[i][j] == 'O') safe[i][j] = true, q.push({i, j});
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int a = x + dx[k], b = y + dy[k];
if (a >= 0 && b >= 0 && a < R && b < C && g[a][b] == 'O' && !safe[a][b]) safe[a][b] = true, q.push({a, b});
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++)
if (g[i][j] == 'O' && !safe[i][j]) g[i][j] = 'X';
cout << g[i] << "\n";
}
return 0;
}Python solution
import sys
from collections import deque
data = sys.stdin.read().split()
R, C = int(data[0]), int(data[1])
g = [list(row) for row in data[2 : 2 + R]]
safe = [[False] * C for _ in range(R)]
q = deque()
for i in range(R):
for j in range(C):
if (i in (0, R - 1) or j in (0, C - 1)) and g[i][j] == "O":
safe[i][j] = True
q.append((i, j))
while q:
x, y = q.popleft()
for a, b in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
if 0 <= a < R and 0 <= b < C and g[a][b] == "O" and not safe[a][b]:
safe[a][b] = True
q.append((a, b))
for i in range(R):
print("".join("X" if g[i][j] == "O" and not safe[i][j] else g[i][j] for j in range(C)))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int R = sc.nextInt(), C = sc.nextInt();
char[][] g = new char[R][];
for (int i = 0; i < R; i++) g[i] = sc.next().toCharArray();
boolean[][] safe = new boolean[R][C];
ArrayDeque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if ((i == 0 || j == 0 || i == R - 1 || j == C - 1) && g[i][j] == 'O') {
safe[i][j] = true;
q.add(new int[] {i, j});
}
int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
while (!q.isEmpty()) {
int[] p = q.poll();
for (int k = 0; k < 4; k++) {
int a = p[0] + dx[k], b = p[1] + dy[k];
if (a >= 0 && b >= 0 && a < R && b < C && g[a][b] == 'O' && !safe[a][b]) {
safe[a][b] = true;
q.add(new int[] {a, b});
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) sb.append(g[i][j] == 'O' && !safe[i][j] ? 'X' : g[i][j]);
sb.append('\n');
}
System.out.print(sb);
}
}