POJ 3278 Catch That Cow（BFS）

题目链接：https://cn.vjudge.net/problem/POJ-3278

题意：给你 n 和 k ，可以对 n 进行 n+1、n-1和n*2的操作，问至少经过几次操作数字 n 能够到达 k 。

思路：从n开始BFS，每次将三种操作加入队列搜索，最先搜索到的肯定是操作最少的，由此对已经搜索过的点进行标记剪枝。

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<queue>
 4 #include<cstring>
 5 using namespace std;
 6 const int maxn = 1e5 + 5;
 7 int vis[maxn];
 8 int n,m;
 9 struct node{
10     int num,dep;
11 };
12 bool check(int x)
13 {
14     if(x >= 0 && x < maxn  && !vis[x]) return true;
15     else return false;
16 }
17 int BFS(int x)
18 {
19     memset(vis,0,sizeof(0));
20     node a,next;
21     a.num = x,a.dep = 0;
22     queue<node> q;
23     q.push(a);
24     while(!q.empty())
25     {
26         a = q.front();q.pop();
27         if(a.num == m) return a.dep;
28         next = a;
29         next.num = a.num + 1;
30         if(check(next.num))
31         {
32             next.dep = a.dep + 1;
33             vis[next.num] = 1;
34             q.push(next);
35         }
36         next.num = a.num - 1;
37         if(check(next.num))
38         {
39             next.dep = a.dep + 1;
40             vis[next.num] = 1;
41             q.push(next);
42         }
43         next.num = a.num * 2;
44         if(check(next.num))
45         {
46             next.dep = a.dep + 1;
47             vis[next.num] = 1;
48             q.push(next);
49         }
50     }
51     return -1;
52 }
53 int main()
54 {
55     cin >> n >> m;
56     cout << BFS(n);
57     return 0;
58 }

POJ 3278 Catch That Cow（BFS）

相关推荐