Poj 3278 农夫追牛
题目链接
已知农夫坐标为N，母牛坐标为K。每次农夫有三种移动方式，可移动到 X-1,X+1,2X 上，问最少需要移动多少次农夫可以移动到K。
对于移动次数的最小值问题，通常采用BFS求解
即遍历每一层，如果当前层数得到目标方案，即中止搜索。该层的层高最低，次数最小。
首先，如果一个坐标已经走过了，那下一次一定不会再走这个坐标。因为N—>X—>K 比 N—>X—>Y—>X—>K更优，我们需要明确在步数最少的情况下，选定了一个坐标后以后的走法是唯一的，只跟当前坐标有关，而与之前怎么到该坐标方式无关。即在最优走法时，一个坐标点只会被经历一次。(有点像环，你好不容易走了很久，却又回到原点。那么之前的努力都白费了，一定不是最优解)
并且使用BFS搜索的好处就在于，每个坐标在第一次被访问时，就是访问到该节点的最小次数，如果后续再访问到该点，可以剪枝排除（因为搜索情况和当前是一摸一样的）。因此使用 $ vis[ N ] $ 数组记录每个坐标的访问情况。
然而该题目有一个很trick的地方在于:如果能通过2X超过K后再倒退得到最小值，那么其中一个最优的走法满足2X最多比t大一（最优的走法不唯一）
假设现在位置为X
分奇数偶数证明：
-
偶数：
如果2X后比K大2n，按该方法会+1（变成2X 的那一步）+2n（倒退）= 1+2n；
则我可以先让X后退n步，再变成2X，即 $ 2（X-n） $ 。代价 n+1 比方法一更优（当且仅当n=0时取等），且满 足变成2x后，距离与K等于0<=1
此时距离为0
-
奇数：
如果2X后比K大2n+1, 按该方法会+1（变成2X的那一步）+2n+1（倒退）=2+2n；
则我可以通过先后退n步，再加倍走，再后退一步，代价**+n+2**(当且仅当n=0时取等)
此时距离为1
-
所以坐标范围限制在0到K+1 ！！！大大减少了搜索范围，否则就像我一样timeout了
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include<iostream>
#include<queue>
using namespace std;
int n,t;
int ans=1000000;
#define N 200003
int a[N];
int vis[N];
struct node
{
int a;
int deep;
node(int x1,int d1)
{
a=x1;
deep=d1;
}
};
queue<node> q;
void bfs()
{
while(!q.empty())
{
node tmp=q.front();
q.pop();
if(tmp.a==t)
{
cout<<tmp.deep;
break;
}
for(int i=1;i<=3;i++)
{
if(i==1)
{
int x=tmp.a+1;
int d=tmp.deep;
if(!vis[x]&&0<=x&&x<=t+1)
{
vis[x]=1;
q.push(node(x,d+1));
}
}
else if(i==2)
{
int x=2*tmp.a;
int d=tmp.deep;
if(!vis[x]&&0<=x&&x<=t+1)
{
vis[x]=1;
q.push(node(x,d+1));
}
}
else
{
int x=tmp.a-1;
int d=tmp.deep;
if(!vis[x]&&0<=x&&x<=t+1)
{
vis[x]=1;
q.push(node(x,d+1));
}
}
}
}
}
int main()
{
cin>>n>>t;
if(n==t)
{
cout<<0<<endl;
}
else if(t<n)
{
cout<<(n-t)<<endl;
}
else
{
q.push(node(n,0));
vis[n]=1;
bfs();
}
}
|