2 条题解
-
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
- 难度
- 5
- 标签
- (无)
- 递交数
- 147
- 已通过
- 62
- 上传者