机试练习01：poj3278 —— 农夫和牛问题

参考来源：https://blog.csdn.net/king_way/article/details/33305017

一、题解方法

采用BFS。

因为农夫每次移动的代价相同，而广度优先搜索算法在权值一样时的解即为最佳解，所以此题用广度优先搜索算法就可以解决了。

将农夫每次的选择看成一个三叉树，即-1，+1，2。农夫的初始节点为树的根节点，然后依次访问当前节点的三个孩子（+1，-1，2），每访问一个节点时将该节点放入队列以实现广度优先搜索。最佳解出现时跳出循环。

程序设置一个待访问坐标队列（实现广搜），一个坐标是否访问标志和一个距离数组（每个点到农夫起点的最短距离）。

二、题解代码

[ 复制代码

](javascript:void(0); "复制代码")

<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: "Courier New" !important; font-size: 12px !important;"> 1 #include "stdio.h"
2 #include "stdlib.h"
3 #include "math.h"
4 #include <string.h>
5 #include <algorithm>
6 #include <iostream>
7
8 using namespace std; 9
10 int head, tail; 11 int queue[100001]; 12 int dist[100001]; 13 bool flag[100001]; 14
15 bool empty() 16 { 17 if(head == tail) 18 return true; 19 else
20 return false; 21 } 22
23 void en_queue(int x) 24 { 25 queue[tail++] = x; 26 } 27
28 int de_queue() 29 { 30 return queue[head++]; 31 } 32
33 int main() { 34
35 int n, k; 36 scanf("%d%d", &n, &k); 37
38 int temp; 39
40 head = tail = 0; 41
42 memset(dist, 0,sizeof(dist)); 43 memset(flag,0,sizeof(flag)); 44 memset(queue,0,sizeof(queue)); 45
46 en_queue(n); 47 flag[n] = true; 48
49 while(empty() == false) 50 { 51 n = de_queue(); 52
53 if(n == k) 54 { 55 printf("%d", dist[n]); 56 break; 57 } 58
59 temp = n+1; 60 if(flag[temp] == false && temp <= 100000) 61 { 62 flag[temp] = true; 63 dist[temp] = dist[n] + 1; 64 en_queue(temp); 65 } 66
67 temp = n-1; 68 if(flag[temp] == false && temp >= 0) 69 { 70 flag[temp] = true; 71 dist[temp] = dist[n] + 1; 72 en_queue(temp); 73 } 74
75 temp = n*2; 76 if(flag[temp] == false && temp <= 100000) 77 { 78 flag[temp] = true; 79 dist[temp] = dist[n] + 1; 80 en_queue(temp); 81 } 82 } 83
84
85 return 0; 86 }</pre>

[ 复制代码

](javascript:void(0); "复制代码")