ʕ·͡ˑ·ཻ ʕ•̫͡• ʔ•̫͡•ཻʕ•̫͡•ʔ•͓͡•ʔ

27:抓住那头牛

描述

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：

1、从X移动到X-1或X+1，每次移动花费一分钟

2、从X移动到2*X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

输入

两个整数，N和K

输出

一个整数，农夫抓到牛所要花费的最小分钟数

样例输入

1
5 17

样例输出

1
4

解题：

​ 虽然是道很简单的搜索题，但坑点很多

​ 1.判断牛在人的左边还是右边

​ 2.数组开大一点

​ 3.判断是否越界

​ 否则会一直RE

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;

struct node {
	int x, t;
};
//之前开的1e5 + 10,很神奇，反正是不行
int vis[1000010];
node st, ne, en;

int BFS() {
	queue <node> q;
	q.push(st);
	while(!q.empty()) {
		st = q.front();
		q.pop();
		if(st.x == en.x) return st.t;
		ne.x = st.x + 1;
        //要判断点是否在范围内
		if(ne.x >= 0 && !vis[ne.x] && ne.x <= 100000) {
		ne.t = st.t + 1; 
		q.push(ne);
		vis[ne.x] = 1;
	}
		ne.x = st.x - 1;
		if(ne.x >= 0 && !vis[ne.x] && ne.x <= 100000) {
			ne.t = st.t + 1;
			q.push(ne);
			vis[ne.x] = 1;
		}
		ne.x = st.x * 2;
		if(ne.x >= 0 && !vis[ne.x] && ne.x <= 100000) {
			ne.t = st.t + 1;
			q.push(ne);
			vis[ne.x] = 1;		
	}
}
}

int main() {
	int n, k;
	cin>>n>>k;
    //这里也要注意
	if(n >= k) {
		cout<<n-k<<endl;
		return 0;
	}
	st.x = n;
	st.t = 0;
	en.x = k;
	vis[st.x] = 1;
	cout<<BFS()<<endl;
	return 0;
}

 Previous

广搜