Posted on 2023-01-25 03:01
Uriel 阅读(23)
评论(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