Video Solution

By David Zhou

Explanation

We can BFS from the starting point of A and check if we can reach B. If we reach B, we must have done it in the shortest path possible.

Implementation

Time Complexity: $\mathcal{O}(NM)$

Copy
from collections import deque

MAX_N = 1000
STEP_DIR = "URDL"

# 0 = up, 1 = right, 2 = down, 3 = left
DX = [-1, 0, 1, 0]
DY = [0, 1, 0, -1]

vis = [[False for _ in range(MAX_N)] for _ in range(MAX_N)]