Surrounded regions

from collections import deque
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        visited = set()
        rows = len(board)
        cols = len(board[0])
        q = deque() 
        for i in range(rows):
            if board[i][0] == "O":
                board[i][0] = "A"
                q.append((i, 0))
            if board[i][cols - 1] == "O":
                board[i][cols - 1] = "A"
                q.append((i, cols - 1))
        for i in range(cols):
            if board[0][i] == "O":
                board[0][i] = "A"
                q.append((0, i))
            if board[rows - 1][i] == "O":
                board[rows - 1][i] = "A"
                q.append((rows - 1, i))

        while q:
            x, y = q.popleft()
            for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                newx, newy = x + dx, y + dy
                if 0 <= newx < rows and 0 <= newy < cols and board[newx][newy] == "O":
                    q.append((newx, newy))
                    board[newx][newy] = "A"

        for i in range(rows):
            for j in range(cols):
                if board[i][j] == "A":
                    board[i][j] = "O"
                elif board[i][j] == "O":
                    board[i][j] = "X"

Surrounded Regions

---

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

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

 

Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.

Example 2:

Input: board = [["X"]]
Output: [["X"]]

 

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] is 'X' or 'O'.