Snakes and Ladders
franklinqin0 BFS
# Solution
Let be the length of the square matrix board
.
# Implicit Graph
Complexity
time:
space:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
# flatten 2D board to 1D board_line
board_line = [-1]
for i in reversed(range(n)):
if (n-i) % 2:
col_range = range(n)
else:
col_range = reversed(range(n))
for j in col_range:
board_line.append(board[i][j])
dist = {1:0}
for i in range(2, n**2+1):
dist[i] = sys.maxsize
queue = [1]
while queue:
head = queue.pop(0)
if head == n**2: return dist[head]
for i in range(1, 7):
npos = min(head + i, n**2)
# fly once if snake & ladder exist
if board_line[npos] != -1:
npos = board_line[npos]
# update dist & queue
if npos <= n**2 and dist[npos] > dist[head] + 1:
dist[npos] = dist[head] + 1
queue.append(npos)
return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31