Posted on 2023-01-25 03:01
Uriel 閱讀(43)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
閑來無事重切Leet Code
給出一個2D迷宮（之字形編號），-1代表可以走的空格子，每次可以走[curr + 1, min(curr + 6, n2)]步，其中還有一些蛇形鏈接or梯子，如果走到這些格子則必須跳去蛇or梯子的終點，游戲終點是n*n號格子，問最快幾步可達，BFS
1 #909
2 #Runtime: 261 ms (Beats 11.90%)
3 #Memory: 13.4 MB (Beats 92.86%)
4
5 class Solution(object):
6 def snakesAndLadders(self, board):
7 """
8 :type board: List[List[int]]
9 :rtype: int
10 """
11 vis = set([1])
12 n = len(board)
13 board_linear = []
14 for i in range(n-1, -1, -1):
15 if i%2 != n%2:
16 for j in range(n):
17 board_linear.append(board[i][j])
18 else:
19 for j in range(n-1, -1, -1):
20 board_linear.append(board[i][j])
21 q = deque([(1, 0)])
22 while q:
23 x = q.popleft()
24 for i in range(6):
25 if x[0] + i > n*n:
26 break
27 if board_linear[x[0] + i] == -1:
28 tx = x[0] + i + 1
29 else:
30 tx = board_linear[x[0] + i]
31 if tx == n*n:
32 return x[1] + 1
33 if tx in vis:
34 continue
35 vis.add(tx)
36 q.append((tx, x[1] + 1))
37 return -1