【POJ3278】Catch That Cow-蒲公英云

【POJ3278】Catch That Cow

这里写图片描述

搜索里应用型的题目。
记得考虑临界情况哦。
BFS代码：

#include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
const int N = 100000;
bool vis[N+100];
int n,m;
struct note {
    int t;
    int id;
} s;
bool check(int a) {
    if(a<0||a>N||vis[a])
        return 0;
    return 1;
}
int bfs(int n,int m) {
    queue<note >Q;
    s.t=n,s.id=0;
    Q.push(s);
    vis[s.t]=true;
    while(!Q.empty()) {
        note now,end;
        now=Q.front();
        Q.pop();
        if(now.t==m) {
            return now.id;
        }
        end.t=now.t+1;
        if(check(end.t)) {
            end.id=now.id+1;
            Q.push(end);
            vis[end.t]=true;
        }
        end.t=now.t-1;
        if(check(end.t)) {
            end.id=now.id+1;
            Q.push(end);
            vis[end.t]=true;
        }
        end.t=now.t*2;
        if(check(end.t)) {
            end.id=now.id+1;
            Q.push(end);
            vis[end.t]=true;
        }
    }
    return -1;
}
int main() {
    while(scanf("%d%d",&n,&m)!=EOF) {
        memset(vis,false,sizeof(vis));
        int ans=bfs(n,m);
        printf("%d\n",ans);
    }
    return 0;
}