【POJ3278】Catch That Cow

一时失言乱红尘 2022-09-24 11:25 130阅读 0赞

![这里写图片描述][20160729232524571]  
![这里写图片描述][20160729232538018]

搜索里应用型的题目。  
记得考虑临界情况哦。  
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;
    }

[http://poj.org/problem?id=3278][http_poj.org_problem_id_3278]

[20160729232524571]: /images/20220719/54e5395b5a4945fd8b96a3320918e698.png
[20160729232538018]: /images/20220719/7d063f09620c4bdb86bad3afe20f8a65.png
[http_poj.org_problem_id_3278]: http://poj.org/problem?id=3278