ARST打卡第112周[112/521]

Algorithm

lc909_蛇梯棋

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
// 题意难懂,直接看题解锻炼思维吧
// 简单的bfs,主要是题意离谱
class Solution {
pair<int, int> id2rc(int id, int n) {
int r = (id - 1) / n, c = (id - 1) % n;
if (r % 2 == 1) {
c = n - 1 - c;
}
return {n - 1 - r, c};
}

public:
int snakesAndLadders(vector<vector<int>> &board) {
int n = board.size();
vector<int> vis(n * n + 1);
queue<pair<int, int>> q;
q.emplace(1, 0);
while (!q.empty()) {
auto p = q.front();
q.pop();
for (int i = 1; i <= 6; ++i) {
int nxt = p.first + i;
if (nxt > n * n) { // 超出边界
break;
}
auto rc = id2rc(nxt, n); // 得到下一步的行列
if (board[rc.first][rc.second] > 0) { // 存在蛇或梯子
nxt = board[rc.first][rc.second];
}
if (nxt == n * n) { // 到达终点
return p.second + 1;
}
if (!vis[nxt]) {
vis[nxt] = true;
q.emplace(nxt, p.second + 1); // 扩展新状态
}
}
}
return -1;
}
};

// 作者:LeetCode-Solution
// 链接:https://leetcode-cn.com/problems/snakes-and-ladders/solution/she-ti-qi-by-leetcode-solution-w0vl/

Review

struct python包
https://docs.python.org/3/library/struct.html#format-characters

Struct is a good tool to handle the binary file.

Tips

vscode 切换选中文字的大小写的快捷键

Share

CVAL,PVAL,SVAL宏定义