1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // 最大搜索范围:M最大为1e5,2*M足够覆盖所有有效搜索 const int MAX = 2e5 + 10; // dist[x]:从起点N到位置x的最少步数 int dist[MAX]; int main() { // 关闭cin同步,加速输入 ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; // [1] 读取鸡的位置N、狗的位置M cin >> N >> M; // [2] 特殊情况:鸡在狗的右侧/同一位置,直接向左走即可 if(N >= M) { cout << N - M << endl; return 0; } // [3] 初始化距离数组,-1表示该位置未被访问 memset(dist, -1, sizeof(dist)); queue<int> q; // BFS队列,存储待遍历的位置 // [4] 起点初始化:N的步数为0,入队启动BFS dist[N] = 0; q.push(N); // [5] BFS核心循环,层级遍历所有可达位置 while(!q.empty()) { // 取出队首的当前位置 int x = q.front(); q.pop(); // 遍历3种合法操作,生成下一步的位置 // 操作1:向右走一步 int nx = x + 1; // 合法性检查:位置在有效范围内,且未被访问过 if(nx <= 2*M && dist[nx] == -1) { dist[nx] = dist[x] + 1; if(nx == M) // 到达终点,直接输出结果 { cout << dist[nx] << endl; return 0; } q.push(nx); // 新位置入队 } // 操作2:向左走一步 nx = x - 1; if(nx >= 0 && dist[nx] == -1) { dist[nx] = dist[x] + 1; if(nx == M) { cout << dist[nx] << endl; return 0; } q.push(nx); } // 操作3:飞到2倍位置 nx = x * 2; if(nx <= 2*M && dist[nx] == -1) { dist[nx] = dist[x] + 1; if(nx == M) { cout << dist[nx] << endl; return 0; } q.push(nx); } } return 0; }
- 1
信息
- ID
- 1306
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者