1
# The question is an awesome example of multi-source bfs.
2
# The intuition is to add the boundary to a heap if it is 'O'.
3
# Start the bfs from the nodes added and since you're using queue(FIFO) this bfs will check for inner matrix elements and if they are also 'O' just start
4
# convertin all these 'O's to 'E's.
5
# The last step is to traverse the matrix and if the element is still 'O' turn it to 'X' if it is 'E' turn it to 'O' and we get our answer.
6
# Pro-Tip -> Try to reduce the number of append operations in python. The lesser the append operations the better is the runtime!
7
from collections import deque
8

9

10
class Solution:
11
    def solve(self, bb: List[List[str]]) -> None:
12
        """
13
        Do not return anything, modify board in-place instead.
14
        """
15
        heap = deque()
16
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
17
        r, c = len(bb), len(bb[0])
18
        for i in range(r):
19
            if bb[i][0] == "O":
20
                heap.append((i, 0))
21
            if bb[i][c - 1] == "O":
22
                heap.append((i, c - 1))
23
        for i in range(1, c - 1):
24
            if bb[0][i] == "O":
25
                heap.append((0, i))
26
            if bb[r - 1][i] == "O":
27
                heap.append((r - 1, i))
28
        visited = set()
29

30
        def isValid(nr, nc):
31
            if 0 <= nr < r and 0 <= nc < c:
32
                return True
33
            else:
34
                return False
35

36
        while heap:
37
            ri, ci = heap.popleft()
38
            bb[ri][ci] = "E"
39
            for i, j in directions:
40
                nr, nc = ri + i, ci + j
41
                if isValid(nr, nc) and (nr, nc) not in visited and bb[nr][nc] == "O":
42
                    heap.append((nr, nc))
43
                    visited.add((nr, nc))
44
        for i in range(r):
45
            for j in range(c):
46
                if bb[i][j] == "O":
47
                    bb[i][j] = "X"
48
                if bb[i][j] == "E":
49
                    bb[i][j] = "O"