# Surrounded Regions

## Problem

Given a 2D board containing `'X'` and `'O'` (**the letter O**), capture all regions surrounded by `'X'`.

A region is captured by flipping all `'O'`s into `'X'`s in that surrounded region.

![](/files/-MQcs2A9pAqNsDOGE_hT)

### Thought Process

* Have to use DFS since we are dealing with connected components here. The important part is the connected components that will be using DFS on are the border 'O' and the other 'O' that are connected to them.

* Use DFS on the borders to find all the connected 'O' and initally chage all these connected components to something else to denote the connectivity to the border 'O' (like change them to 'C')

* After all the border DFS is completed, run back through the board and change all 'C' to 'O'. The original 'O' 's that weren't changed to 'C' are the valid regions that can be flipped. So we flip these to 'X'.

## Solution

```
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if len(board) == 0:
            return 
        
        for i in range(len(board)):
            self.dfs(board,i,0)
            self.dfs(board,i,len(board[0])-1)
            
        for j in range(len(board[0])):
            self.dfs(board,0,j)
            self.dfs(board,len(board)-1,j)
            
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'C':
                    board[i][j] = 'O'
                elif board[i][j] == 'O':
                    board[i][j] = 'X'
            
            
    def dfs(self, board, i, j):
        if board[i][j] == 'O':
            
            board[i][j] = 'C'
            if i > 1: self.dfs(board, i-1, j)
            if i+1 < len(board): self.dfs(board, i+1, j)
            if j > 1: self.dfs(board, i, j-1)
            if j+1 < len(board[0]): self.dfs(board, i, j+1)
```

## Time Complexity

* **Time:** O(m\*n)
* **Space:** O(m\*n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://joshualbarb.gitbook.io/leetcode-problems/graphs/surrounded-regions.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.