【題解】POJ 3278 Catch That Cow

【題目敘述】https://vjudge.net/problem/POJ-3278
【解題想法】BFS

  • 在數線座標上,每單位時間可以從點 x 移動到 x + 1、x – 1 或 2 * x。
  • dis[ ]:紀錄走到每個點的最短距離。初始值設為INF,表示該點未曾走訪。
  • (Line-18/22/26) 在不超出界限的情況下測試三種移動的可能性。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 100000;
int n, k, dis[maxn+1], now;
queue <int> q;

int main() {
    while (cin >> n >> k){
        memset(dis, 0x3F, sizeof(dis));
        q.push(n);
        dis[n] = 0;
        while (!q.empty()){
            now = q.front();
            q.pop();
            if (now+1 <= maxn && dis[now]+1 < dis[now+1]){
                dis[now+1] = dis[now]+1;
                q.push(now+1);
            }
            if (now-1 >= 0 && dis[now]+1 < dis[now-1]){
                dis[now-1] = dis[now]+1;
                q.push(now-1);
            }
            if (now*2 <= maxn && dis[now]+1 < dis[now*2]){
                dis[now*2] = dis[now]+1;
                q.push(now*2);
            }
        }
        cout << dis[k] << "\n";
    }
}
分享本文 Share with friends