<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>

class Solution:
    directions = [[-1,0],[1,0],[0,-1],[0,1]]
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # 1. Figure out all the regions and record their tiles.
        # 2. Check each region and see if they are "surrounded" or not (ie check if any tiles are on the board's edges)
        # 3. Convert all the surrounded regions to 'X', then return
        surroundedRegions = []
        visited = [[False for x in range(len(board[0]))] for a in range(len(board))]
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'O' and not visited[i][j]:
                    region, isSurrounded = self.bfs(board, visited, i, j)
                    if isSurrounded: # by problem definition we don't want to capture regions not surrounded
                        surroundedRegions.append(region)

        print(f'surrounded regions: {surroundedRegions}')

        for region in surroundedRegions:
            for coords in region:
                board[coords[0]][coords[1]] = 'X'
        return
    
    def bfs(self, board, visited, i, j):
        q = deque()
        region = []
        isSurrounded = True
        
        q.append((i,j))
        while q:
            currI, currJ = q.popleft()
            # print(f'currI: {currI}, currJ: {currJ}')
            
            ### Checks to run before evaluating tile
            if self.isOutOfBounds(currI, 0, len(board) - 1) or self.isOutOfBounds(currJ, 0, len(board[0]) - 1): # this means that it isn't surrounded
                continue
            if board[currI][currJ] != 'O': # shouldn't be accounting for other tiles
                continue
            if visited[currI][currJ]: # don't need to double-count 'O' tiles
                continue
            if self.onEdge(currI, currJ, len(board) - 1, len(board[0]) - 1): # check that tile is not on the edge for surrounded definition
                isSurrounded = False

            visited[currI][currJ] = True
            
            region.append((currI, currJ))
            
            # get curr's neighbors, then add them to q if not out of bounds
            neighbors = self.getNeighbors(currI, currJ)
            for neighborI, neighborJ in neighbors:
                q.append((neighborI, neighborJ))
                # if not self.isOutOfBounds(neighborI, 0, len(board) - 1) and not self.isOutOfBounds(neighborJ, 0, len(board[0]) - 1):
                #     q.append((neighborI, neighborJ))
        
        # print(f'region: {region}, isSurrounded: {isSurrounded}')
        return region, isSurrounded

    def onEdge(self, i, j, rowEdge, colEdge):
        if i == 0 or i >= rowEdge or j == 0 or j >= colEdge:
            return True
        return False
        
    def getNeighbors(self, i, j):
        neighbors = []
        for currDir in self.directions:
            neighbors.append((i + currDir[0], j + currDir[1]))
        return neighbors
    
    def isOutOfBounds(self, i, start, end):
        if i < 0 or i > end:
            return True
        return False
21170