Minimum Moves to Move a Box to Their Target Location LeetCode solution in Python

1
class Solution:
2
    def minPushBox(self, grid: List[List[str]]) -> int:
3
        m, n = len(grid), len(grid[0])
4
        q = deque()
5
        start, target, box = (0, 0), (0, 0), (0, 0)
6
        for i in range(m):
7
            for j in range(n):
8
                if grid[i][j] == "B":
9
                    box = (i, j)
10
                elif grid[i][j] == "T":
11
                    target = (i, j)
12
                elif grid[i][j] == "S":
13
                    start = (i, j)
14
        q.append((box[0], box[1], 0, start[0], start[1]))
15
        visited = set()
16
        directions = ((1, 0, -1, 0), (0, 1, 0, -1), (-1, 0, 1, 0), (0, -1, 0, 1))
17
        visited.add(box + box)
18

19
        def solve(i, j, bi, bj):
20
            nonlocal seen
21
            if (i, j) == (bi, bj):
22
                return True
23
            ans = False
24
            for d in directions:
25
                ni, nj = i + d[0], j + d[1]
26
                if (
27
                    0 <= ni < m
28
                    and 0 <= nj < n
29
                    and (ni, nj) not in seen
30
                    and grid[ni][nj] != "#"
31
                ):
32
                    seen.add((ni, nj))
33
                    ans = ans or solve(ni, nj, bi, bj)
34
                    if ans:
35
                        return ans
36
            return ans
37

38
        while q:
39
            i, j, pushes, si, sj = q.popleft()
40
            if (i, j) == target:
41
                return pushes
42
            if pushes > m + n:
43
                return -1
44
            for d in directions:
45
                ni, nj, bi, bj = i + d[0], j + d[1], i + d[2], j + d[3]
46
                if (
47
                    0 <= ni < m
48
                    and 0 <= nj < n
49
                    and (ni, nj, i, j) not in visited
50
                    and grid[ni][nj] != "#"
51
                    and 0 <= bi < m
52
                    and 0 <= bj < n
53
                    and grid[bi][bj] != "#"
54
                ):
55
                    seen = set()
56
                    seen.add((i, j))
57
                    grid[i][j] == "#"
58
                    res = solve(si, sj, bi, bj)
59
                    grid[i][j] = "."
60
                    if not res:
61
                        continue
62
                    visited.add((ni, nj, i, j))
63
                    q.append((ni, nj, pushes + 1, i, j))
64
        return -1