11852 - Knight's Trip

問題概要

十分に広いチェス盤の上でナイトが(0,0)から任意の座標(x,y)まで動くとき、最小何回の移動で(x,y)まで到達できるだろうか。x,yは最大でも10億とする。

コード

#include<iostream>
#include<cmath>
#include<string>
#include<sstream>

#define WHITE 0
#define BLACK 1

using namespace std;

int color(int  x, int y)
{
  return ( abs(x)+abs(y) ) % 2 == 0 ? WHITE : BLACK;
}

int minimumStep(int x, int y)
{
  int step;
  x=abs(x);
  y=abs(y);

  if( x == 0 && y == 0 ) return 0;
  if( x == 1 && y == 0 || x == 0 && y == 1 ) return 3;
  if( x == 2 && y == 2 ) return 4;

  if( 2*x < y || 2*y < x ){
    step = max(x,y)/2;
    if(max(x,y)%2!=0)++step;
  }else{
    step=(x+y)/3;
    if((x+y)%3!=0)++step;
  }
  
  if(color(x,y)==color(0,0)){
    if(step%2!=0){
      ++step;
    }
  }else if(color(x,y)!=color(0,0)){
    if(step%2==0){
      ++step;
    }
  }
  return step;
}

int main()
{
  while(true){
    int x,y;
    string s;
    getline(cin,s);
    if( s == "END" ) break;
    istringstream iss(s);
    iss >> x >> y;
    
    int ans = minimumStep(x,y);
    cout << ans << endl;
  }
  return 0;
}

解法

まずナイトの動きの対称性から第1象限に限定する。小さな範囲で求めると規則性が分かる。次に、ある場所へ行くのに少なくともnステップかかるとすると、そのような場所は反時計回りに(2n-1,0)-(2n,0)-(2n,n)-(n,2n)-(0,2n)-(0,2n-1)-(n-1,2n-1)-(2n-1,n-1)と点を結んだ境界線を含む領域の内部の点であることがわかる。実際にはこの領域は3つに分けられる。その内二つは(2n-1,0)-(2n,0)-(2n,n-1)-(2n-1,n-1)と(0,2n-1)-(n-1,2n-1)-(n-1,2n)-(0,2n)で、この長方形内にあるような(x,y)は2*x