2279040_re.cpp

北大大牛代码 1240道题的原代码 超级权威

# include <iostream>

using namespace std;

int si, sj, ei, ej, l;

void bfs()
{
	int queue[10001][3];
	int i, j, w = 0;
	int f, r;
	int mark[101][101];

	f = r = -1;
	memset(mark,0,sizeof(mark));
	mark[si][sj] = 1;
	queue[++f][0] = si,queue[f][1] = sj;queue[f][2] = 0;
	while(f!=r)
	{
		++r;
		i = queue[r][0],j = queue[r][1],w = queue[r][2];
		if(i-1>=0)
		{
			if(j-2>=0)
			{
				if(mark[i-1][j-2]==0)
				{
					mark[i-1][j-2] = 1;
					queue[++f][0]=i-1,queue[f][1]=j-2,queue[f][2]=w+1;
					if(i-1==ei&&j-2==ej)
						break;
				}
			}
			if(j+2<l)
			{
				if(mark[i-1][j+2]==0)
				{
					mark[i-1][j+2] = 1;
					queue[++f][0]=i-1,queue[f][1]=j+2,queue[f][2]=w+1;
					if(i-1==ei&&j+2==ej)
						break;
				}
			}
		}
		if(i-2>=0)
		{
			if(j-1>=0)
			{
				if(mark[i-2][j-1]==0)
				{
					mark[i-2][j-1] = 1;
					queue[++f][0]=i-2,queue[f][1]=j-1,queue[f][2]=w+1;
					if(i-2==ei&&j-1==ej)
						break;
				}
			}
			if(j+1<l)
			{
				if(mark[i-2][j+1]==0)
				{
					mark[i-2][j+1] = 1;
					queue[++f][0]=i-2,queue[f][1]=j+1,queue[f][2]=w+1;
					if(i-2==ei&&j+1==ej)
						break;
				}
			}
		}
		if(i+1<l)
		{
			if(j-2>=0)
			{
				if(mark[i+1][j-2]==0)
				{
					mark[i+1][j-2] = 1;
					queue[++f][0]=i+1,queue[f][1]=j-2,queue[f][2]=w+1;
					if(i+1==ei&&j-2==ej)
						break;
				}
			}
			if(j+2<l)
			{
				if(mark[i+1][j+2]==0)
				{
					mark[i+1][j+2] = 1;
					queue[++f][0]=i+1,queue[f][1]=j+2,queue[f][2]=w+1;
					if(i+1==ei&&j+2==ej)
						break;
				}
			}
		}
		if(i+2<l)
		{
			if(j-1>=0)
			{
				if(mark[i+2][j-1]==0)
				{
					mark[i+2][j-1] = 1;
					queue[++f][0]=i+2,queue[f][1]=j-1,queue[f][2]=w+1;
					if(i+2==ei&&j-1==ej)
						break;
				}
			}
			if(j+1<l)
			{
				if(mark[i+2][j+1]==0)
				{
					mark[i+2][j+1] = 1;
					queue[++f][0]=i+2,queue[f][1]=j+1,queue[f][2]=w+1;
					if(i+2==ei&&j+1==ej)
						break;
				}
			}
		}
	}
	cout<<w+1<<endl;
}

int main()
{
	int n;

	cin>>n;
	while(n--)
	{
		cin>>l>>si>>sj>>ei>>ej;
		if(si!=ei||sj!=ej)
			bfs();
		else
			cout<<"0\n";
	}
	return 1;
}