DSA · Graphs · #175
Surrounded Regions
Module 55 · difficulty 3/5·⏱ 30:00starts on first keystroke
Given an `m x n` board containing `'X'` and `'O'`, capture all regions that are 4-directionally surrounded by `'X'`. A region is captured by flipping all `'O'`s into `'X'`s in that surrounded region. A region is **surrounded** if none of its `'O'` cells touches the border of the board. Implement `solve(board)` which modifies `board` **in place** and returns nothing. Any `'O'` connected (horizontally or vertically) to a border `'O'` is safe; every other `'O'` is flipped to `'X'`.
Examples
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]→[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]— The three middle 'O's are surrounded and flipped. The bottom 'O' touches the border, so it stays.board = [["X"]]→[["X"]]— No 'O' to flip.board = [["O","O"],["O","O"]]→[["O","O"],["O","O"]]— Every 'O' touches the border, so nothing is captured.
Constraints
- · m == board.length
- · n == board[i].length
- · 1 <= m, n <= 200
- · board[i][j] is 'X' or 'O'.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.