首页 > 代码库 > Knight's Trip 马在无线大棋盘上跳到指定点最小步数问题
Knight's Trip 马在无线大棋盘上跳到指定点最小步数问题
题目描述
Problem D: 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 wordEND.
输出要求
For each location in the input, output a line containing one integer, the minimum number of moves required for a knight to move from (0,0) to (x,y).
假如输入
1 2
2 4
END
应当输出
1
2
这题不能用bfs,bfs代码如下,因为棋盘很大,会空间不足,但可以用bfs打印出棋盘来状况来分析,这题做了好久- -、、、、
#include<iostream> #include<algorithm> #include <vector> #include<string.h> #include<ctype.h> #include<math.h> using namespace std; int map[1005][1005]; int res[1005][1005]; struct point { int x,y; }; struct point r[1005]; int dis[8][2]={{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}}; int m,n; void bfs() { int tail=1, head=0,i,x1,y1; r[0].x=2; r[0].y=2; while(tail != head) { x1=r[head].x; y1=r[head].y; for(i=0; i<8; i++) { x1+=dis[i][0], y1+=dis[i][1]; if(map[x1][y1]==0&&res[x1][y1]==-1) { r[tail].x=x1; r[tail].y=y1; res[x1][y1] = 1 + res[x1-dis[i][0]][y1-dis[i][1]]; tail++; } x1-=dis[i][0], y1-=dis[i][1]; } head++; if(res[m+2][n+2]!=-1) break; } } void fun(); int main() { fun(); return 0; } void fun() { int i,j; while(cin>>m>>n) { memset(map,-1,sizeof(map)); memset(res,-1,sizeof(res)); m=abs(m); n=abs(n); if(m>n) { int temp=m; m=n; n=temp; } for(i=2;i<m+3;i++) { for(j=2;j<n+3;j++) map[i][j]=0; } res[2][2]=0;//棋盘0,0点 res[3][3]=2;//棋盘1,1坐标要自己赋值,否则bfs算出来是4是错误的,因为我们把棋盘只考虑成第一象限的了 bfs(); for(i=2;i<m+3;i++) { for(j=2;j<n+3;j++) printf("%3d",res[i][j]); cout<<endl; } cout<<res[m+2][n+2]<<endl; } }
可以用枚举来解决,如下
n=2*m这种情况直接就是(m+n)/3步。
如果n<2*m但是(m+n)%3==0的话,那么我们可以通过控制(1,2),(2,1)两种跳法的次数达到...总数必然是(m+n)/3,然后m,n的和对3取余是1的话,我们是不是必然可以在(m+n-1)/3步的时候跳到(m,n-1)这个点,但是不能一步跳到(m,n),回撤两步到(m-4,n-5)这个点,我们可以用三步跳到(m,n),那么就是原先的步数+1。余数为2,就是先跳到(m-1,n-1)这个地方,我们知道(0,0)到(1,1)只需要两步,那么(m-1,n-1)到(m,n)也就是原先步数+2.
然后考虑n>2*m,先把(0,1)的情况特殊处理一下。接着我们可以用m步跳到(m,n),那么原问题就转化为(0,0)到(0,n-2*m)。当n-2*m是4的倍数的话我们可以直接(1,2)(-1,2)这个跳可以在(n-2*m)/2步到达。余数为1,就是(0,0)到(0,1)的问题,但是这个需要三步不是最优的,我们后撤两步变为(0,0)到(0,5),我们可以三步达到,那么就是原先的步数加上1就是解。余数为2,我们可以分别跳一次(2,1)(-2,1)到达。余数为3,转化为(0,0)到(0,3)的问题我们可以(-1,2)(1,1)(0,3)三步到达。
#include<iostream> #include<algorithm> #include <vector> #include<string.h> #include<ctype.h> #include<math.h> using namespace std; void fun(); int main() { fun(); return 0; } void fun() { int m,n; while(cin>>m>>n) { m=abs(m); n=abs(n); if(m>n) { int temp=m; m=n; n=temp; } if(2*m>=n) { if(m==n&&m==1) cout<<2<<endl; else if(m==n&&m==2) cout<<4<<endl; else cout<<(m+n)/3+(m+n)%3<<endl; } else { int ans=m; int c=(n-2*m)%4; ans+=c; ans+=(n-2*m-c)/2; if(n==1&&m==0) ans=3; cout<<ans<<endl; } } }
Knight's Trip 马在无线大棋盘上跳到指定点最小步数问题