首页 > 代码库 > Knight's Trip 马在无线大棋盘上跳到指定点最小步数问题

Knight's Trip 马在无线大棋盘上跳到指定点最小步数问题

2024-08-07 00:03:02   221人阅读

题目描述

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 马在无线大棋盘上跳到指定点最小步数问题


联系
我们