我的小破站欢迎各位访问哦~
这道题是一道BFS的题目
初始时人在N点,罪犯在K点,求从N点抓到罪犯的最短时间
有三种走法
1.向前1步,耗费时间1
2.向后1步,耗费时间1
3.向前2步,耗费时间1
分为两种情况
1.人在罪犯后面,然后枚举三种走法计算步数,每一步都在前一步时间的基础是加1
2.人在罪犯的前面,所以只有一种走法就是向后走,耗费时间就是n-k
#include<iostream> #include<cstdlib> #include<cstring> #include<queue> using namespace std; int step[100010]; bool vis[100010]; int n, k; queue<int>q; int bfs(int n, int k) { int head, next; q.push(n); vis[n] = 1; step[n] = 0; while (!q.empty()) { head = q.front(); q.pop(); for (int i = 0; i < 3; i++) { if (i == 0) { next = head + 1; } else if (i == 1) { next = head - 1; } else { next = head * 2; } if (next < 0 || next>100010) continue; if (!vis[next]) { q.push(next); step[next] = step[head] + 1; vis[next] = 1; } if (next == k) return step[next]; } } } int main() { while (cin >> n >> k) { memset(step, 0, sizeof(step)); memset(vis, 0, sizeof(vis)); if (n >=k) { cout << n - k<<endl; } else { cout << bfs(n, k) << endl; } } return 0; }
