(Sky OJ) 144. Day 3 PF. 宿命的對決

https://pc2.tfcis.org/sky/index.php/problem/view/144/

DP or BFS

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

const int MAX_N = 1e5 + 6;

int dp[MAX_N];

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        memset(dp,-1,sizeof(dp));
        int a,b;
        scanf("%d %d",&a,&b);
        if (a==b || a>=b) {
            printf("%lld\n",a-b+1);
            continue;
        }
        dp[a] = 0;
        queue<int> que;
        que.push(a);
        int dx[3] = {1,1,2};
        int dy[3] = {1,-1,0};
        while (!que.empty()) {
            int t=que.front();
            que.pop();
            for (int i=0;3>i;i++) {
                int tt=t*dx[i]+dy[i];
                if (tt>b) {
                    if (dp[b]==-1) dp[b] = dp[t] + abs(b-tt)+1;
                    else {
                        dp[b] = min(dp[b],dp[t] + abs(b-tt)+1);
                    }
                }
                else if (tt <= 0) ;
                else if (dp[tt] == -1 || dp[tt]>dp[t]) {
                    dp[tt] = dp[t] + 1;
                    que.push(tt);
                }
            }
        }
        printf("%d\n",dp[b]+1);
    }
}