VIRTUALS

the virtual labs for the virtuals

0%

LeetCode 909. 蛇梯棋

Posted on Edited on In , ,

摘要：
BFS魔改题。

题目

$N \times N$ 的棋盘 $board$ 上，按从 $1$ 到 $N \times N$ 的数字给方格编号，编号 从左下角开始，每一行交替方向。

例如，一块 $6 \times 6$ 大小的棋盘，编号如下：

0x0

$r$ 行 $c$ 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；如果 $board[r][c] != -1$，那个蛇或梯子的目的地将会是 $board[r][c]$。

玩家从棋盘上的方格 $1$ （总是在最后一行、第一列）开始出发。

每一回合，玩家需要从当前方格 $x$ 开始出发，按下述要求前进：

  • 选定目标方格：选择从编号 $x+1$，$x+2$，$x+3$，$x+4$，$x+5$，或者 $x+6$ 的方格中选出一个目标方格 $s$ ，目标方格的编号 $<= N \times N$。

    • 该选择模拟了掷骰子的情景，无论棋盘大小如何，你的目的地范围也只能处于区间 $[x+1, x+6]$ 之间。

  • 传送玩家：如果目标方格 $S$ 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 $S$。
    注意，玩家在每回合的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，你也不会继续移动。

返回达到方格 $N \times 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。

提示：

  • $2 <= board.length = board[0].length <= 20$
  • $board[i][j]$ 介于 $1$ 和 $N \times N$ 之间或者等于 $-1$。
  • 编号为 $1$ 的方格上没有蛇或梯子。
  • 编号为 $N \times N$ 的方格上没有蛇或梯子。

BFS

这道题很容易看出来是一道利用BFS找到最短路径步数的题目。和一般的BFS题不同之处在于引入了「传送门」的概念，以及搜索方向是蛇形的。
引入「传送门」的概念并不妨碍最先BFS到终点的路径一定最短这一BFS特性。
重要的是，我们还是要标记出已经到达的位置，以避免重复入队。
把棋盘上非 $-1$ 的数字看成一个位置指针，也不必考虑到循环指针的问题。因为只要做好重复标记，可以避免所有循环指针入队。

我和yxc解法的区别主要在于路径长度记录和重复标记方法。
对于路径长度记录，我是将路径长度和路径点坐标放在一起入队，每次搜索下一个点，将路径 $+1$；而yxc是维护一个和原棋盘大小相同的每个值初始化为无穷大的 dist 二维数组，将起点设为 $0$，每搜索到一个点，如果是新的点，就在当前点的距离上 $+1$。

对于重复标记，我是将已入队的位置在原棋盘上更改为一个特定值 0x3f3f3f3f；而yxc的解法利用记录路径长度的二维数组，如果搜索到的新点对应值是无穷大，说明确实是一个新的点，如果不是，则之前已被搜过。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
 * 2021-6-27 18:12:16
 * author: etoa
 */
static const auto shutdown = []() {
    cin.tie(nullptr)->sync_with_stdio(false);
    return nullptr;
}();


class Solution {
public:
    int R, C;

    static constexpr int N = 404;
    pair<pair<int, int>, int> q[N];
    int hh = 0, tt = -1;

    unordered_map<int, pair<int, int>> heap;

    int snakesAndLadders(vector<vector<int>>& board) {
        this->R = board.size(), this->C = board[0].size();

        vector<vector<int>> grid(R, vector<int>(C, 0));
        int last = 0;
        for (int r = R - 1; r >= 0; r--) {
            int c = ((-r + R) & 1) ? 0 : C - 1;
            for (; c >= 0 && c < C; last++) {
                grid[r][c] = last + 1;
                heap[last + 1] = {r, c};
                if ((-r + R) & 1) c++;
                else c--;
            }
        }

        int target = R * C;
        q[++tt] = {{R - 1, 0}, 0};
        board[R - 1][0] = 0x3f3f3f3f;
        for (; tt >= hh; hh++) {
            int r = q[hh].first.first, c = q[hh].first.second;
            int x = grid[r][c];
            int cnt = q[hh].second;
            
            ++cnt;
            for (int i = 1; i <= 6; i++) {
                int nex = x + i;
                int ner = heap[nex].first, nec = heap[nex].second;
                //cout << "ner: " << ner << " nec: " << nec << " nex: " << nex << " cnt: " << cnt << endl;
                if (nex == target || board[ner][nec] == target) {
                    return cnt;
                }
                if (nex > target || board[ner][nec] == 0x3f3f3f3f) continue;
                // determine teleport beacon
                if (board[ner][nec] > 0) {
                    q[++tt] = {heap[board[ner][nec]], cnt};
                }
                else {
                    q[++tt] = {{ner, nec}, cnt};
                }
                board[ner][nec] = 0x3f3f3f3f;
            }
        }
        return -1;
    }
};
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
 * author: yxc@acwing
 */
#define x first
#define y second

typedef pair<int, int> PII;

class Solution {
public:
    vector<vector<int>> id;
    vector<PII> cor;

    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size(), m = board[0].size();
        id = vector<vector<int>>(n, vector<int>(m));
        cor = vector<PII>(n * m + 1);
        for (int i = n - 1, k = 1, s = 0; i >= 0; i --, s ++ ) {
            if (s % 2 == 0) {
                for (int j = 0; j < m; j ++, k ++ ) {
                    id[i][j] = k;
                    cor[k] = {i, j};
                }
            } else {
                for (int j = m - 1; j >= 0; j --, k ++ ) {
                    id[i][j] = k;
                    cor[k] = {i, j};
                }
            }
        }

        queue<PII> q;
        vector<vector<int>> dist(n, vector<int>(m, 1e9));
        q.push({n - 1, 0});
        dist[n - 1][0] = 0;
        while (q.size()) {
            auto t = q.front();
            q.pop();

            int k = id[t.x][t.y];
            if (k == n * m) return dist[t.x][t.y];
            for (int i = k + 1; i <= k + 6 && i <= n * m; i ++ ) {
                int x = cor[i].x, y = cor[i].y;
                if (board[x][y] == -1) {
                    if (dist[x][y] > dist[t.x][t.y] + 1) {
                        dist[x][y] = dist[t.x][t.y] + 1;
                        q.push({x, y});
                    }
                } else {
                    int r = board[x][y];
                    x = cor[r].x, y = cor[r].y;
                    if (dist[x][y] > dist[t.x][t.y] + 1) {
                        dist[x][y] = dist[t.x][t.y] + 1;
                        q.push({x, y});
                    }
                }
            }
        }
        return -1;
    }
};

原题链接： LeetCode 909. 蛇梯棋