<p>You are given an <code>n x n</code> integer matrix <code>board</code> where the cells are labeled from <code>1</code> to <code>n<sup>2</sup></code> in a <a href="https://en.wikipedia.org/wiki/Boustrophedon" target="_blank"><strong>Boustrophedon style</strong></a> starting from the bottom left of the board (i.e. <code>board[n - 1][0]</code>) and alternating direction each row.</p>

<p>You start on square <code>1</code> of the board. In each move, starting from square <code>curr</code>, do the following:</p>

<ul>
	<li>Choose a destination square <code>next</code> with a label in the range <code>[curr + 1, min(curr + 6, n<sup>2</sup>)]</code>.

	<ul>
		<li>This choice simulates the result of a standard <strong>6-sided die roll</strong>: i.e., there are always at most 6 destinations, regardless of the size of the board.</li>
	</ul>
	</li>
	<li>If <code>next</code> has a snake or ladder, you <strong>must</strong> move to the destination of that snake or ladder. Otherwise, you move to <code>next</code>.</li>
	<li>The game ends when you reach the square <code>n<sup>2</sup></code>.</li>
</ul>

<p>A board square on row <code>r</code> and column <code>c</code> has a snake or ladder if <code>board[r][c] != -1</code>. The destination of that snake or ladder is <code>board[r][c]</code>. Squares <code>1</code> and <code>n<sup>2</sup></code> are not the starting points of any snake or ladder.</p>

<p>Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do <strong>not</strong> follow the subsequent&nbsp;snake or ladder.</p>

<ul>
	<li>For example, suppose the board is <code>[[-1,4],[-1,3]]</code>, and on the first move, your destination square is <code>2</code>. You follow the ladder to square <code>3</code>, but do <strong>not</strong> follow the subsequent ladder to <code>4</code>.</li>
</ul>

<p>Return <em>the least number of moves required to reach the square </em><code>n<sup>2</sup></code><em>. If it is not possible to reach the square, return </em><code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/09/23/snakes.png" style="width: 500px; height: 394px;" />
<pre>
<strong>Input:</strong> board = [[-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]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> 
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> board = [[-1,-1],[-1,3]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == board.length == board[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 20</code></li>
	<li><code>board[i][j]</code> is either <code>-1</code> or in the range <code>[1, n<sup>2</sup>]</code>.</li>
	<li>The squares labeled <code>1</code> and <code>n<sup>2</sup></code> are not the starting points of any snake or ladder.</li>
</ul>

from collections import deque

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        # 计算棋盘的大小（边长）
        n = len(board)
        
        # 用于存储每个格子对应的坐标 (行, 列)
        cells = [None] * (n**2 + 1)
        
        # 棋盘格子的编号，1号格子开始
        label = 1
        
        # 从左到右列的顺序（会在每行遍历后反转）
        columns = list(range(0, n))
        
        # 从棋盘的最后一行向上遍历
        for row in range(n - 1, -1, -1):
            # 遍历当前行的所有列
            for column in columns:
                # 将当前编号的格子与对应的 (行, 列) 关联
                cells[label] = (row, column)
                # 编号递增
                label += 1
            # 当遍历完当前行后，将列的顺序反转（模拟蛇形棋盘）
            columns.reverse()
        
        # 距离数组，初始化为 -1，表示未访问
        dist = [-1] * (n * n + 1)
        
        # 使用双端队列（deque）初始化，起点是第1号格子
        q = deque([1])
        
        # 起点格子的距离设为 0
        dist[1] = 0
        
        # 开始广度优先搜索
        while q:
            # 从队列中弹出当前格子编号
            curr = q.popleft()
            
            # 尝试从当前格子走 1 到 6 步，计算下一个格子
            for next in range(curr + 1, min(curr + 6, n**2) + 1):
                # 通过 next 找到对应的棋盘坐标 (行, 列)
                row, column = cells[next]
                
                # 判断是否有梯子或蛇，若有则直接跳转到指定的目的地；否则就到达 next 自己
                destination = (board[row][column] if board[row][column] != -1 else next)
                
                # 如果这个目的地格子还没有被访问过
                if dist[destination] == -1:
                    # 将该格子标记为已访问，并记录从起点到此的步数
                    dist[destination] = dist[curr] + 1
                    # 将该格子加入队列中，进行下一步的搜索
                    q.append(destination)
        
        # 返回到达最后一个格子的步数，如果为 -1 说明无法到达
        return dist[n * n]

16400