POJ 1915 - Knight Moves

http://poj.org/problem?id=1915

概要

\(l \times l\) の盤面上にスタート位置とゴール位置が与えられるので， ナイトの動きに従って移動したときの最小ステップ数を答える．

制約

• \(4 \le l \le 300\)

解法

BFS するだけ．

 1 #include <cstdio>
 2 #include <queue>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int T;
 9   scanf("%d", &T);
10   while (T-- > 0) {
11     int L;
12     scanf("%d", &L);
13     pair<int,int> start, goal;
14     scanf("%d %d", &start.first, &start.second);
15     scanf("%d %d", &goal.first, &goal.second);
16     static int dist[300][300];
17     static const int INF = 10000000;
18     for (int i = 0; i < L; i++) {
19       fill_n(dist[i], L, INF);
20     }
21     dist[start.first][start.second] = 0;
22     queue<pair<int,int> > q;
23     q.push(start);
24     while (!q.empty()) {
25       const int i = q.front().first;
26       const int j = q.front().second;
27       q.pop();
28       for (int d = 0; d < 8; d++) {
29         static const int di[] = {-2, -1, 1, 2, 2, 1, -1, -2};
30         static const int dj[] = {1, 2, 2, 1, -1, -2, -2, -1};
31         const int k = i + di[d];
32         const int l = j + dj[d];
33         if (0 <= k && k < L && 0 <= l && l < L && dist[i][j]+1 < dist[k][l]) {
34           dist[k][l] = dist[i][j]+1;
35           q.push(make_pair(k, l));
36         }
37       }
38     }
39     printf("%d\n", dist[goal.first][goal.second]);
40   }
41   return 0;
42 }