C++ 编程：解决蛇梯棋游戏的最少投掷次数

#include #include #include using namespace std;

const int MAXN = 10005; int n, s, t; int dis[MAXN]; bool vis[MAXN]; int snake[MAXN], ladder[MAXN];

void bfs() { memset(dis, -1, sizeof(dis)); // 初始化距离为-1 memset(vis, false, sizeof(vis)); // 初始化访问标记为false dis[0] = 0; // 起点距离为0 queue q; q.push(0); // 将起点入队 while (!q.empty()) { int x = q.front(); q.pop(); vis[x] = false; // 将该点标记为未在队列中 for (int i = 1; i <= 6; i++) { // 枚举骰子的点数 int y = x + i; // 计算下一步的位置 if (y > n) continue; // 如果超出终点，则不考虑 if (snake[y] != -1) y = snake[y]; // 如果遇到蛇头，则直接跳到蛇尾 if (ladder[y] != -1) y = ladder[y]; // 如果遇到梯子底部，则直接跳到梯子顶部 if (dis[y] == -1 || dis[y] > dis[x] + 1) { // 如果该位置未到达或者更新距离更短 dis[y] = dis[x] + 1; // 更新距离 if (!vis[y]) { // 如果该点未在队列中 q.push(y); // 入队 vis[y] = true; // 标记为已入队 } } } } }

int main() { cin >> n >> s; memset(snake, -1, sizeof(snake)); for (int i = 0; i < s; i++) { int x, y; cin >> x >> y; snake[x] = y; } cin >> t; memset(ladder, -1, sizeof(ladder)); for (int i = 0; i < t; i++) { int x, y; cin >> x >> y; ladder[x] = y; } bfs(); cout << dis[n] << endl; return 0; }