Pattern Recognition Drill
Medium Graphs
The Problem
Given a board of 'X' and 'O', capture all regions surrounded by 'X' (flip 'O' to 'X'), except those connected to the border.
What approach would you use?
Think about it before scrolling down.
Mark border-connected O's as safe (DFS from borders). Then flip all remaining O's to X. O(m*n).
BFS from border O's. Same logic.
Common Trap
Don't try to detect 'surrounded' regions directly. Instead, find 'unsurrounded' from the border and flip the rest.