POJ 1915 knight Moves

問題
http://poj.org/problem?id=1915
ナイトの動きで何手で目的地までいけるかを計算せよ

解法
BFS
移動先座標を配列で持っておくのがコツ

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

typedef pair<int,int> P;
const int INF = 1 << 29;
const int dx[8] = {-2,-2,-1,-1,1,1,2,2};
const int dy[8] = {-1,1,-2,2,-2,2,-1,1};
int sx, sy;
int gx, gy;
int l;
int main(){
	int N;
	scanf("%d", &N);
	for(int c=0; c<N; ++c){
		int ans = -1;
		scanf("%d", &l);
		scanf("%d %d %d %d", &sx, &sy, &gx, &gy);
		int board[300][300];
		for(int i=0; i<l; ++i)
			fill(board[i], board[i]+l, INF);
		board[sx][sy] = 0;
		queue<P> Q;
		Q.push(P(sx, sy));
		while(!Q.empty()){
			int x = Q.front().first, y = Q.front().second; Q.pop();
			int d = board[x][y];
			if(x == gx && y == gy){
				ans = d;
				break;
			}
			for(int i=0; i<8; ++i){
				int nx = x+dx[i], ny = y+dy[i];
				if(nx == gx && ny == gy){
					ans = d + 1;
					break;
				}
				if(0<=nx&&nx<l && 0<=ny&&ny<l && board[nx][ny] == INF){
					board[nx][ny] = d + 1;
					Q.push(P(nx, ny));
				}
			}
			if(ans != -1) break;
		}
		printf("%d\n", ans);
	}
	return 0;
}