読者です 読者をやめる 読者になる 読者になる

川のブログ

川の適当気ままなブログです。 

AOJ 0594 Super Metropolis

こんにちは川です。

今回は、最短の道を求める問題ですね。

斜めの道が使えないとき(今いる場所と次の場所が 左上、右下 にあるとき)は

マンハッタン距離で、

斜めの道に進める場合はx座標かy座標のどちらかと同じになるまで斜めで進み、

余った道を足せば答えにたどりつきます。

 

ソースコード

 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int w,h,n;
    cin>>w>>h>>n;
    int x[2],y[2];
    cin>>x[0]>>y[0];
    int ans=0;
    for(int i=1;i<n;i++){
        cin>>x[1]>>y[1];
        if(x[0]<x[1]&&y[0]<y[1]||x[0]>x[1]&&y[0]>y[1]){
            int kawa=min(abs(x[1]-x[0]),abs(y[1]-y[0]));
            ans+=kawa+max(abs(x[1]-x[0])-kawa,abs(y[1]-y[0])-kawa);
        }
        else ans+=abs(x[0]-x[1])+abs(y[0]-y[1]);
        x[0]=x[1];
        y[0]=y[1];
    }
    cout<<ans<<endl;
}