记录编号	153528	评测结果	AAAAAAAAAA
题目名称	[HNOI 2006]马步距离	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2015-03-18 06:12:42	内存使用	0.32 MiB

/****************************************\
* Author : ztx
* Title  : [bzoj] 1193: [HNOI2006]马步距离
* ALG    : 贪心 bfs 搜索
* CMT    : 大范围贪心跳,小范围bfs
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}

#define Abs(x) ((x)<0?(-(x)):(x))

#define  ii  std::pair<int,int>

#include <queue>

const int dx[8] = {1,2,1,2,-1,-2,-1,-2} ;
const int dy[8] = {2,1,-2,-1,2,1,-2,-1} ;

#define  maxn  51LL

int dis[51][51] = {0} ;
std::queue< ii > q ;

void bfs(int x , int y) {
int tx , ty , i ;
	q.push(ii(x,y)) ;
	while (!q.empty()) {
		x=q.front().first , y=q.front().second ;
		q.pop() ;
		if (x==5&&y==5) return ;
		Rep (i,0,7) {
			tx=x+dx[i] , ty=y+dy[i] ;
			if (tx<1||ty<1||tx>50||ty>50) continue ;
			if (!dis[tx][ty] || dis[tx][ty]>dis[x][y]+1) {
				dis[tx][ty] = dis[x][y]+1 ;
				q.push(ii(tx,ty)) ;
			}
		}
	}
}

int sx , sy , x , y , cnt ;

int main() {
	#define READ
	#ifdef  READ
		freopen("horsed.in" ,"r",stdin ) ;
		freopen("horsed.out","w",stdout) ;
	#endif
	read(sx) , read(sy) , read(x) , read(y) ;
	x -= sx , y -= sy ;
	if (x < 0) x = -x ;
	if (y < 0) y = -y ;
	cnt = 0 ;
	while (Abs(x)+Abs(y) > 30) {
/*大范围贪心*/
		if (x > y) { cnt++ ; x-- , x-- , y-- ; }
		else { cnt++ ; x-- , y-- , y-- ; }
		if (x<0) x = -x ;
		if (y<0) y = -y ;
	}
	x += 5 , y += 5 ;
	dis[x][y] = cnt ;
	/*这时bfs找dis(5,5)*/
	bfs(x,y) ;
	printf("%d\n", dis[5][5]) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}