首页 > 代码库 > hdu 2717 Catch That Cow
hdu 2717 Catch That Cow
---恢复内容开始---
Catch That Cow
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14433 Accepted Submission(s):
4396
Problem Description
Farmer John has been informed of the location of a
fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤
100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the
same number line. Farmer John has two modes of transportation: walking and
teleporting.
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes
for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.题意:在一条自然数列上,农夫约翰站在数列上的某一个点,点坐标为N,他的牛站在坐标为K的一个点上,现在约翰有三种走法走到另外的坐标点上,问约翰走到牛所在的那一格位置至少需要走几步。
思路:bfs广度优先搜索,dp[v]代表走到点v需要的最少步数,并且让dp[N]=0,动态转移的找最优解。
AC代码:
#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<algorithm> #include<string> #include<cmath> #include<set> #include<queue> using namespace std; const int N_MAX = 100000+1; set<int>s; queue<int>que; int dp[N_MAX*10]; void bfs(int begin,int end) { s.insert(begin); que.push(begin); while (!que.empty()) { int dx = que.front(); que.pop(); for (int i = 0; i < 3; i++) { int x; switch (i) { case 0: if(dx-1>=0&&dx-1<N_MAX) x = dx - 1; break; case 1: if (dx + 1 < N_MAX&&dx+1>=0) x = dx + 1; break; case 2: if (2*dx>=0&&2 * dx < N_MAX) x = dx * 2; break; } set<int>::iterator it = s.find(x); if (it == s.end()) {//x这个点还没去过 s.insert(x); dp[x] = dp[dx] + 1; if (x == end)return;//找到end,返回 que.push(x); } } } } int main() { int N, K; while (scanf("%d%d", &N, &K)!=EOF) { memset(dp, 0, sizeof(dp)); bfs(N, K); ////// while (!que.empty()) que.pop(); ////// s.clear(); printf("%d\n", dp[K]); } return 0; }
hdu 2717 Catch That Cow
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。