tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

PKU1915 Knight Moves

300*300までの正方形のチェス盤的なものにナイトを置く。
何回でゴールまでたどり着けるか

小さいしBFSでいける。
というか今日BFSばっかりやってる気がする。
DPやらなきゃまずいんじゃないの?

#include<stdio.h>
#include<queue>
#include<algorithm>
#include<math.h>
using namespace std;
int kx[]={-2,-2,-1,-1,1,1,2,2};
int ky[]={1,-1,2,-2,2,-2,1,-1};
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		int table[300][300];
		int l;
		scanf("%d",&l);
		for(int j=0;j<l;j++)
			for(int k=0;k<l;k++)
				table[j][k]=-1;
		
		queue <pair<int,int> > Q;
		int sx,sy;
		scanf("%d%d",&sx,&sy);
		table[sx][sy]=0;
		int gx,gy;
		scanf("%d%d",&gx,&gy);
		Q.push(make_pair(sx,sy));
		while(Q.size()){
			int nowx=Q.front().first;
			int nowy=Q.front().second;
			//printf("%d %d\n",nowx,nowy);
			for(int j=0;j<8;j++)
				if(nowx+kx[j]>=0&&nowx+kx[j]<l&&nowy+ky[j]>=0&&nowy+ky[j]<l&&table[nowx+kx[j]][nowy+ky[j]]==-1){
					table[nowx+kx[j]][nowy+ky[j]]=table[nowx][nowy]+1;
					Q.push(make_pair(nowx+kx[j],nowy+ky[j]));
				}
			Q.pop();
		}
		printf("%d\n",table[gx][gy]);
	}
}