1 条题解
-
0
// 起点入队 // 队列非空且没到终点就继续搜 // 取出队头 // 考虑 now 能走到哪儿 // now-1,能走到,且没走过 // now+1,能走到,且没走过 // now*2,能走到,且没走过
#include <bits/stdc++.h> using namespace std; const int MAXN = 200000; queue<int> q; // 存还需要搜索的点 bool vis[MAXN + 5]; // vis[i] 存 i 这个点搜过了没有 int dis[MAXN + 5]; // dis[i] 存从起点几步能走到 i int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; // 人的起点,牛的位置 cin >> n >> k; // 起点入队 q.push(n); vis[n] = true; dis[n] = 0; // 队列非空且没到终点就继续搜 while (!q.empty() && !vis[k]) { // 取出队头 int now = q.front(); q.pop(); // 考虑 now 能走到哪儿 // now-1,能走到,且没走过 if (0 <= now - 1 && now - 1 <= MAXN && vis[now - 1] == false) { vis[now - 1] = true; dis[now - 1] = dis[now] + 1; q.push(now - 1); } // now+1,能走到,且没走过 if (0 <= now + 1 && now + 1 <= MAXN && vis[now + 1] == false) { vis[now + 1] = true; dis[now + 1] = dis[now] + 1; q.push(now + 1); } // now*2,能走到,且没走过 if (0 <= now * 2 && now * 2 <= MAXN && vis[now * 2] == false) { vis[now * 2] = true; dis[now * 2] = dis[now] + 1; q.push(now * 2); } } cout << dis[k]; return 0; }
- 1
信息
- ID
- 472
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- (无)
- 递交数
- 165
- 已通过
- 70
- 上传者