1
class Solution:
2
    def orangesRotting(self, grid: List[List[int]]) -> int:
3
        visited = set()
4
        res = 0
5

6
        def bfs(grid):
7
            que = collections.deque()
8
            for i in range(len(grid)):
9
                for j in range(len(grid[0])):
10
                    if grid[i][j] == 2:
11
                        que.append((i, j))
12
            que.append(None)
13
            count = 0
14
            while len(que) > 0:
15
                left, right = 0, 0
16
                # This other while loop is to make sure that we traverse from all the rotten oranges in one turn.
17
                while que[0] != None:
18
                    r, c = que.popleft()
19
                    for Cols in [-1, 1]:
20
                        if (
21
                            c + Cols >= 0
22
                            and c + Cols < len(grid[0])
23
                            and grid[r][c + Cols] == 1
24
                        ):
25
                            grid[r][c + Cols] = 2
26
                            left += 1
27
                            que.append((r, c + Cols))
28

29
                    for Rows in [-1, 1]:
30
                        if (
31
                            r + Rows >= 0
32
                            and r + Rows < len(grid)
33
                            and grid[r + Rows][c] == 1
34
                        ):
35
                            grid[r + Rows][c] = 2
36
                            right += 1
37
                            que.append((r + Rows, c))
38
                            """
39
                if either left or right or both is incremented it means that we have moved in either direction,
40
                and then this will be counted as a turn(or minute as per the problem description.).
41

42
                """
43
                if left is not 0 or right is not 0:
44
                    count += 1
45
                que.popleft()
46
                if len(que) > 0:
47
                    """
48
                    This is required to terminate the loop and prevent infinite loop.
49
                    This only appends a None if there is still some values in the que,
50
                    else we have completed our traversal and we can stop going any futher.
51
                    """
52
                    que.append(None)
53
            return count
54

55
        res = bfs(grid)
56
        for i in range(len(grid)):
57
            for j in range(len(grid[0])):
58
                if grid[i][j] == 1:
59
                    return -1
60
        return res