用C++写代码完成任务本关任务：找出赢得给定 Snake and Ladder 棋盘游戏所需的最少投掷次数规则说明起始位置为0棋盘上的格子编号为1~n终点为n依据骰子的数字确定前移的步数如果恰好到达梯子的底部则自动前移至梯子顶部如果恰好遇到蛇的头部则自动回退至蛇的尾部。编程要求根据提示在右侧编辑器补充代码首先输入棋盘上的格子数量n然后输入蛇的数量s以及每一条蛇的首尾位置x和y接着输入梯子的数量t以

#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; }