Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. An O region survives exactly when it touches the border.
  2. 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);
    }
}

Solve Surrounded Regions online · All practice problems