POJ3278 Catch That Cow（BFS）

January 15, 2016

题目链接

题意：起点为 n，终点为 k。运动有三个方向：n-1，n+1，2*n。最少几步到达 k 点。

思路：BFS 三个方向。额外要注意的是剪枝和 n 等于 k 时答案应为 0。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxx = 100005;
int n, k, ans, next;
bool vis[maxx];     //标记是否访问过
struct point{
    int x, n;       //x为坐标，n为布数
};
void bfs(){
    if(n == k){
        ans = 0;
        return;
    }
    queue<point> q;
    point p1;
    p1.x = n;
    p1.n = 0;
    q.push(p1);
    vis[n] = 1;
    while(!q.empty()){
        point p2 = q.front();
        q.pop();
        for(int i = 0; i < 3; i++){
            if(!i)
                next = p2.x + 1;
            else if(i == 1)
                next = p2.x - 1;
            else next = 2*p2.x;
            if(next < 0 || next > maxx) continue;  //剪枝
            if(next == k){
                ans = p2.n+1;
                return;
            }
            if(!vis[next]){
                point p3;
                p3.x = next;
                p3.n = p2.n+1;
                q.push(p3);
                vis[next] = 1;
            }

        }
    }
}
int main(){
    //freopen("a.txt", "r", stdin);
    while(scanf("%d %d", &n, &k) != EOF){
        memset(vis, 0, sizeof(vis));
        bfs();
        cout << ans << endl;
    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]