Surrounded Regions

**Problem Statement:** Given the required input arguments, write an efficient algorithm to solve the **Surrounded Regions** problem. Implement the required logic as specified by standard definitions for this classic algorithmic challenge. **Hint / Expected Approach:** BFS from border 'O's, mark safe; flip rest **Edge Cases to Consider:** - (1) No 'O's - (2) 'O' on every border - (3) Single 'O' in center

Examples

Example 1

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

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

Explanation: Inner O flipped, border O kept

Example 2

Input: [["X"]]

Output: [["X"]]

Explanation: Single X

Example 3

Input: [["O"]]

Output: [["O"]]

Explanation: Single O (border), kept

Constraints

▪2 <= vertices <= 1000
▪0 <= edges <= 5000
▪Avoid infinite cycles during depth traversal

Watch Out For Edge Cases

▪No 'O's
▪'O' on every border
▪Single 'O' in center

Frequently Asked At

AmazonMicrosoftAdobe

Back to Arena

medium

Graph