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; }