2015
04-10

# Knight’s Trip

In chess, each move of a knight consists of moving by two squares horizontally and one square vertically, or by one square horizontally and two squares vertically. A knight making one move from location (0,0) of an infinite chess board would end up at one of the following eight locations: (1,2), (-1,2), (1,-2), (-1,-2), (2,1), (-2,1), (2,-1), (-2,-1).

Starting from location (0,0), what is the minimum number of moves required for a knight to get to some other arbitrary location (x,y)?

Each line of input contains two integers x and y, each with absolute value at most one billion. The integers designate a location (x,y) on the infinite chess board. The final line contains the word END.

Each line of input contains two integers x and y, each with absolute value at most one billion. The integers designate a location (x,y) on the infinite chess board. The final line contains the word END.

1 2
2 4
END

1
2

#include<stdio.h>
#include<string.h>
int main()
{
char c[20];
while(scanf("%s",c),c[0]!='E')
{
int x=0,y,flag=1;
int k;
for(int i=0;c[i];i++)
{
if(c[i]=='-'&&i==0)
flag=-1;
else
x=x*10+c[i]-48;
}
x=x*flag;
scanf("%d",&y);
if(x<0)
x=-x;
if(y<0)
y=-y;
if(y<x) {k=x;x=y;y=k;}
if(y<=2*x)
{
if(x==1&&y==1)
printf("2\n");
else if(x==2&&y==2)
printf("4\n");
else
printf("%d\n",(x+y)/3+(x+y)%3);
}
else
{
int ans=x;
int c=(y-2*x)%4;
ans+=c;
ans+=(y-2*x-c)/2;
if(y==1&&x==0)
ans=3;
printf("%d\n",ans);
}
}
return 0;
}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)

3. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

4. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示