Leetcode 909 Snakes and Ladders

发表于 |

在一块 N x N 的板子 board 上，从板的左下角开始，每一行交替方向，按从 1 到 N*N 的数字给方格编号。例如，对于一块 6 x 6 大小的板子，可以编号如下：

36 35 34 33 32 31
25 26 27 28 29 30
24 23 22 21 20 19
13 14 15 16 17 18
12 11 10 09 08 07
01 02 03 04 05 06

从板子的方块 1 开始（总是在最后一行、第一列）出发。
从方块 x 开始，每一次移动都按照以下规则：

  1. 你选择一个目标方块 S，它的编号是 x+1，x+2，x+3，x+4，x+5，或者 x+6，只要这个数字满足 <= N*N。
  2. 如果 S 有一个坡或梯子，你就移动到那个坡或梯子的目的地。否则，你会移动到 S。
    在 r 行 c 列上的方格里有 “坡” 或 “梯子”；如果 board[r][c] != -1，那个坡或梯子的目的地将会是 board[r][c]。 注意，你每次移动最多只能爬过一个坡或梯子一次：就算目的地是另一个坡或梯子的起点，你也不会继续移动。
    返回达到方格 N*N 所需的最少移动次数，如果不可能，则返回 -1。

输入：[
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]]
输出：4
解释：
首先，从方格 1 [第 5 行，第 0 列] 开始。
你决定移动到方格 2，并必须爬过梯子移动到到方格 15。
然后你决定移动到方格 17 [第 3 行，第 5 列]，必须爬过坡到方格 13。
然后你决定移动到方格 14，且必须通过梯子移动到方格 35。
然后你决定移动到方格 36, 游戏结束。
可以证明你需要至少 4 次移动才能到达第 N*N 个方格，所以答案是 4。

提示：

  1. 2 <= board.length = board[0].length <= 20
  2. board[i][j] 介于 1 和 N*N 之间或者等于 -1。
  3. 编号为 1 的方格上没有坡或梯子。
  4. 编号为 N*N 的方格上没有坡或梯子。

题意分析：
从方格1开始移动，终点为方格N*N。每一次移动有6种选择，例如当前位于方格X上，则下一步可以到方格X+1,X+2,…,X+6上。但若移动到的方格上的值不等于-1，则需跳到这个值对应的方格上，求最少移动次数。
在多选择路径上找最小移动次数，显然是bfs方法。每次就像下6个方格中移动，一旦方格值不等于-1就跳到方格值对应的方格（注意别重复计算）。唯一要处理的就是方格的index如何跟board中的下标对应起来了（规律很简单，就是蛇形方格）
PS：我对bfs算法在这片博客里有比较详细的介绍，有兴趣的可以参考一下
https://buptwc.github.io/2018/07/24/bfs%E7%B3%BB%E5%88%97%E8%AF%A6%E8%A7%A3/

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
class Solution(object):
    def snakesAndLadders(self, grid):
        m,n = len(grid),len(grid[0])
        # 将index转换成对应的下标
        def transIndex(index):
            x,y = index // n, index % n
            if x % 2 == 0:
                if y != 0: return (m-1-x,y-1)
                return (m-x, 0)
            else:
                if y != 0: return (m-1-x,n-y)
                return (m-x, n-1)

        Q = collections.deque([1])
        level = 0
        visited = set()
        while Q:
            for i in range(len(Q)):
                index = Q.popleft()
                if index == m*n: return level
                for x in range(index+1,index+7):
                    if x <= m*n:
                        i,j = transIndex(x)
                        if grid[i][j] != -1: x = grid[i][j]
                        if x not in visited:
                            visited.add(x)
                            Q.append(x)
            level += 1
        return -1