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