Knight Moves(0)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1915

size
x0 y0
x1 y1

大きさがsize*sizeのチェス盤で、ナイトが(x0,y0)から(x1,y1)まで移動する場合の最小移動回数を求める問題。全方向探索だと相当時間がかかるのだけれども、算術的に求められるらしい。なので超高速。

#include<stdio.h>
#include<stdlib.h>

#define MAX(x,y) (x)>(y)?(x):(y)
#define MIN(x,y) (x)<(y)?(x):(y)

int f(int size, int x0,int y0,int x1,int y1)
{
  int dx = MIN(abs(x0-x1),abs(y0-y1));
  int dy = MAX(abs(x0-x1),abs(y0-y1));
  int corner=0;
  
  if( dx==0 && dy==0 ) return 0;

  if( (x0==0 || x0==size-1) && (y0==0 || y0==size-1) )++corner;
  if( (x1==0 || x1==size-1) && (y1==0 || y1==size-1) )++corner;

  if( corner==2 && size==4 && (dx==0 || dy==0) ) return 5;
  if( dy==1 && dx==1 ) return corner ? 4 : 2;
  if( dy==1) return 3;
  if( dx==2 && dy==2 ) return 4;

  if( dx>dy/2 )
    return (dx+dy)%2 ? (dx+dy+1)/6*2+1 : (dx+dy+4)/6*2;
  else
    return (dx+dy)%2 ? (dy+1)/4*2+1 : (dy+3)/4*2;

}

main()
{
  int t,size,x0,y0,x1,y1;

  for(scanf("%d",&t);t--;)
  {
    scanf("%d%d%d%d%d",&size,&x0,&y0,&x1,&y1);
    printf("%d\n", f(size, x0, y0, x1, y1));
  }
}

あまり縮める気にはならない(;´д｀)