Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理