<p>You are given an <code>m x n</code> matrix <code>board</code> containing <strong>letters</strong> <code>&#39;X&#39;</code> and <code>&#39;O&#39;</code>, <strong>capture regions</strong> that are <strong>surrounded</strong>:</p>

<ul>
	<li><strong>Connect</strong>: A cell is connected to adjacent cells horizontally or vertically.</li>
	<li><strong>Region</strong>: To form a region <strong>connect every</strong> <code>&#39;O&#39;</code> cell.</li>
	<li><strong>Surround</strong>: The region is surrounded with <code>&#39;X&#39;</code> cells if you can <strong>connect the region </strong>with <code>&#39;X&#39;</code> cells and none of the region cells are on the edge of the <code>board</code>.</li>
</ul>

<p>A <strong>surrounded region is captured</strong> by replacing all <code>&#39;O&#39;</code>s with <code>&#39;X&#39;</code>s in the input matrix <code>board</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = [[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;O&quot;,&quot;O&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;X&quot;,&quot;O&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;O&quot;,&quot;X&quot;,&quot;X&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;O&quot;,&quot;X&quot;,&quot;X&quot;]]</span></p>

<p><strong>Explanation:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/19/xogrid.jpg" style="width: 367px; height: 158px;" />
<p>In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = [[&quot;X&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;X&quot;]]</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == board.length</code></li>
	<li><code>n == board[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>board[i][j]</code> is <code>&#39;X&#39;</code> or <code>&#39;O&#39;</code>.</li>
</ul>


def is_on_edge(matrix, coord):
    x, y = coord
    return (
        x == 0 or x == len(matrix[0]) - 1 or y == 0 or y == len(matrix) - 1
    )

def get_up(matrix, coord):
    x,y = coord
    return (x, y-1) if y > 0 else None

def get_down(matrix, coord):
    x,y = coord
    return (x, y+1) if y < len(matrix) - 1 else None

def get_left(matrix, coord):
    x,y = coord
    return (x - 1, y) if x > 0 else None

def get_right(matrix, coord):
    x,y = coord
    return (x + 1, y) if x < len(matrix[0]) - 1 else None

def get_cell(matrix, coord):
    x,y = coord
    return matrix[y][x]

def set_cells_to_x(matrix, coords):
    for x, y in coords:
        matrix[y][x] = 'X'

class Solution:
    def solve(self, matrix: List[List[str]]) -> None:
        if len(matrix) < 3 or (matrix and len(matrix[0]) < 3):
            return matrix

        remaining_o_coords = set()
        for y, row in enumerate(matrix):
            for x, cell in enumerate(row):
                if cell == 'O':
                    remaining_o_coords.add((x, y))

        while remaining_o_coords:
            queue = set([list(remaining_o_coords)[0]])
            all_reachable = set()
            can_reach_edge = False

            while queue:
                # print('---')
                # print('remaining_o_coords:', remaining_o_coords)
                o_coord = queue.pop()
                # print('o_coord:', o_coord)
                remaining_o_coords.remove(o_coord)
                # print('remaining_o_coords:', remaining_o_coords)
                all_reachable.add(o_coord)
                # print('all_reachable:', all_reachable)

                if is_on_edge(matrix, o_coord):
                    can_reach_edge = True

                up_coord = get_up(matrix, o_coord)
                down_coord = get_down(matrix, o_coord)
                left_coord = get_left(matrix, o_coord)
                right_coord = get_right(matrix, o_coord)

                if up_coord in all_reachable:
                    up_coord = None
                if down_coord in all_reachable:
                    down_coord = None
                if left_coord in all_reachable:
                    left_coord = None
                if right_coord in all_reachable:
                    right_coord = None

                if up_coord and get_cell(matrix, up_coord) == 'O':
                    queue.add(up_coord)
                if down_coord and get_cell(matrix, down_coord) == 'O':
                    queue.add(down_coord)
                if left_coord and get_cell(matrix, left_coord) == 'O':
                    queue.add(left_coord)
                if right_coord and get_cell(matrix, right_coord) == 'O':
                    queue.add(right_coord)

                # print('queue:', queue)

            if not can_reach_edge:
                set_cells_to_x(matrix, list(all_reachable))

        return matrix
24230