First mark all 'O' cells reachable from the grid borders as safe using DFS or BFS.

Surrounded Regions

medium

Acceptance: 42%

GraphsDFSBFS

A grid of characters contains 'X' and 'O'. Capture every group of 'O' cells that is fully enclosed by 'X' on all four sides by converting those 'O' cells to 'X'. Groups of 'O' that touch any edge of the grid must not be captured.

Examples

Example 1:

Input:board = [["X","X","X"],["X","O","X"],["X","X","X"]]

Output:[["X","X","X"],["X","X","X"],["X","X","X"]]

Explanation: The center O is completely surrounded and gets captured.

Example 2:

Input:board = [["O","X"],["X","O"]]

Output:[["O","X"],["X","O"]]

Explanation: Both O cells touch the border, so neither is captured.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Surrounded Regions

Examples

Hints

Related Problems