LeetCode 130: Surrounded Regions — Step-by-Step Visual Trace

Medium — Depth-First Search | Matrix | Graph Traversal | Flood Fill The Problem Given a 2D board containing 'X' and 'O', capture all regions of 'O' that are completely surrounded by 'X' by flipping them to 'X'. Regions connected to the border cannot be captured. Approach Use DFS to mark all 'O' cells connected to the border as 'E' (escaped). Then traverse the entire board: flip remaining 'O' cells to 'X' (captured) and restore 'E' cells back to 'O' (escaped). This reverse approach identifies uncapturable regions first. Time: O(m×n) · Space: O(m×n) Code class Solution : def solve ( self , board : List [ List [ str ]]) -> None : def dfs ( row , col ): if ( row < 0 or row >= len ( board ) or col < 0 or col >= len ( board [ 0 ]) or board [ row ][ col ] != " O " ): return board [ row ][ col ] = " E " # Mark as visited but not surrounded # Check adjacent cells dfs ( row + 1 , col ) # Check down dfs ( row - 1 , col ) # Check up dfs ( row , col + 1 ) # Check right dfs ( row , col - 1 ) # Check