3 条题解
-
0
#include <bits/stdc++.h> using namespace std; // 约翰的位置,牛的位置 int n, k; // dis[i] 表示几分钟能走到 i // -1 表示没走过 int dis[200000 + 5]; // 用来广搜的队列 queue<int> q; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k; // 起点入队 for (int i = 0; i <= 200000; i++) dis[i] = -1; dis[n] = 0; q.push(n); // 只要队列非空并且还没走到牛,就继续搜 while (!q.empty() && dis[k] == -1) { // 取出队头 int now = q.front(); q.pop(); // 检查队头一步能到的位置 if (now + 1 <= 200000 && dis[now + 1] == -1) { dis[now + 1] = dis[now] + 1; q.push(now + 1); } if (now - 1 >= 0 && dis[now - 1] == -1) { dis[now - 1] = dis[now] + 1; q.push(now - 1); } if (now * 2 <= 200000 && dis[now * 2] == -1) { dis[now * 2] = dis[now] + 1; q.push(now * 2); } } cout << dis[k]; return 0; }
-
0
#include <bits/stdc++.h> using namespace std; //农夫的位置 n //牛的位置 k int n, k; // i的位置有没有走过 bool vis[2 * 100000 + 10]; // i的位置几分钟能到达 int dis[2 * 100000 + 10]; queue<int> q; int main() { cin >> n >> k; //起点入队 q.push(n); vis[n] = true; dis[n] = 0; //开始广搜:只要队列非空并且没到终点,就继续搜 while (!q.empty() && !vis[k]) { //取出队头 int now = q.front(); q.pop(); //考虑从队头一步能走到哪儿 // now+1:能走且没走过 if (0 <= now + 1 && now + 1 <= 200000 && !vis[now + 1]) { q.push(now + 1); vis[now + 1] = true; dis[now + 1] = dis[now] + 1; } // now-1 if (0 <= now - 1 && now - 1 <= 200000 && !vis[now - 1]) { q.push(now - 1); vis[now - 1] = true; dis[now - 1] = dis[now] + 1; } // now*2 if (0 <= now * 2 && now * 2 <= 200000 && !vis[now * 2]) { q.push(now * 2); vis[now * 2] = true; dis[now * 2] = dis[now] + 1; } } cout << dis[k] << "\n"; return 0; }
-
0
#include <bits/stdc++.h> using namespace std; //农夫的位置 n //牛的位置 k int n, k; // i的位置有没有走过 bool vis[2 * 100000 + 10]; // i的位置几分钟能到达 int dis[2 * 100000 + 10]; //广搜 queue<int> q; void bfs(int st, int ed) { //广搜初始化 memset(vis, false, sizeof(vis)); memset(dis, -1, sizeof(dis)); while (!q.empty()) q.pop(); //起点入队 q.push(st); vis[st] = true; dis[st] = 0; //开始广搜:只要队列非空并且没到终点,就继续搜 while (!q.empty() && !vis[ed]) { //取出队头 int now = q.front(); q.pop(); //考虑从队头一步能走到哪儿 // now+1:能走且没走过 if (0 <= now + 1 && now + 1 <= 200000 && !vis[now + 1]) { q.push(now + 1); vis[now + 1] = true; dis[now + 1] = dis[now] + 1; } // now-1 if (0 <= now - 1 && now - 1 <= 200000 && !vis[now - 1]) { q.push(now - 1); vis[now - 1] = true; dis[now - 1] = dis[now] + 1; } // now*2 if (0 <= now * 2 && now * 2 <= 200000 && !vis[now * 2]) { q.push(now * 2); vis[now * 2] = true; dis[now * 2] = dis[now] + 1; } } } int main() { cin >> n >> k; bfs(n, k); cout << dis[k] << "\n"; return 0; }
- 1
信息
- ID
- 472
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- (无)
- 递交数
- 153
- 已通过
- 65
- 上传者