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;

}