POJ 3278 Catch That Cow（简单BFS）

poj 3278

题目大意 给定一个区间（0~100000），给两个数N，K作为从N到K的起点和终点。每次操作可以+1、-1、*2。问最少多少次操作可以到终点。

分析 把每个数字看成一个状态，一共就 105 个状态，直接广搜就行了。

代码

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<queue> using namespace std; const int INF=999999999; int S,T; int bj[100005]; int step[100005]; void Bfs() { queue<int> Q; Q.push(S); bj[S]=1; step[S]=0; while(!Q.empty()) { int temp=Q.front(); if(temp==T)return ; Q.pop(); if(temp+1<=100000 && bj[temp+1]==0){Q.push(temp+1);bj[temp+1]=1;step[temp+1]=step[temp]+1;} if(temp-1>=0 && bj[temp-1]==0){Q.push(temp-1);bj[temp-1]=1;step[temp-1]=step[temp]+1;} if(temp*2<=100000 && bj[temp*2]==0){Q.push(temp*2);bj[temp*2]=1;step[temp*2]=step[temp]+1;} } } int main() { scanf("%d%d",&S,&T); Bfs(); cout<<step[T]<<endl; }