力扣909. 蛇梯棋

广度优先搜索 + 动态规划

• 思路：
  • 定义 pair {id, step} 为到达格子编号 id，使用的步数 step，记作 step[id]；
  • 记录下所摇骰子 1 - 6 到达的格子编号 next，step[next] = step[id] + 1：
    • 走了 1 步，所能到达的编号；如果中途遇到传送门，直接更新 next 编号；
    • 使用一个数组记录编号是否已经被访问，如果被访问，本着使用步数最少，直接使用上次到达该位置的状态，往后摇骰子即可；
    • 编号没有被访问，则标记染色，同时更新状态 step[next]；
  • 基于这些 step[id] 状态队列，广度优先搜索，动态更新状态，直到到达终点时停止；
  • 获取方格值，需要有一个编号到行列号的映射函数：

    • private:
          std::pair<int, int> id2rc(int id, int n) {
              int row = (id - 1) / n;
              int column = (id - 1) % n;
              if (row % 2 == 1) {
                  column = n - 1 - column;
              }
      
              return {n - 1 - row, column};
          }

    • n - 1 - row 是因为起点是从左下角开始；
    • 因为是左右盘桓，奇偶行的列号发生颠倒；

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();

        std::vector<int> visited(n * n + 1);

        std::queue<std::pair<int, int>> qu;
        qu.emplace(1, 0);
        while (!qu.empty()) {
            auto p = qu.front();
            qu.pop();

            for (int i = 1; i <= 6; ++i) {
                int next = p.first + i;
                if (next > n *n) {
                    break;
                }

                // update next row & column
                auto rc = id2rc(next, n);
                // gateway and passthrough to the dst
                if (board[rc.first][rc.second] > 0) {
                    next = board[rc.first][rc.second];
                }
                // final state
                if (next == n * n) {
                    return p.second + 1;
                }
                if (!visited[next]) {
                    visited[next] = true;
                    qu.emplace(next, p.second + 1);
                }
            }
        }

        return -1;
    }

private:
    std::pair<int, int> id2rc(int id, int n) {
        int row = (id - 1) / n;
        int column = (id - 1) % n;
        if (row % 2 == 1) {
            column = n - 1 - column;
        }

        return {n - 1 - row, column};
    }
};