POJ 1178 - Camelot

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

概要

8 x 8 のボードの上に1体のキングの駒と \(N\) 体のナイトの駒が置かれている． 1つのマスに複数の駒が置かれていても構わない．

1ステップで，いずれかの駒を動かすことができる． キングとナイトが同じマスに存在するとき，キングと1体のナイトを同時に動かすことができる． このときの動かし方はナイトに従う．

キングとナイトの初期位置が与えられたとき，ある1つのマスにすべての駒を集めるのに必要な最小のステップ数を答える．

制約

解法

まずワーシャル・フロイドであるマスから別のマスへナイトが移動するのに必要な最小のステップ数を求めておく．

そして

に関して全探索．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   static const int INF = 10000000;
 9   vector<vector<int> > dist(64, vector<int>(64, INF));
10   for (int i = 0; i < 64; i++) {
11     dist[i][i] = 0;
12     const int x = i/8, y = i%8;
13     for (int d = 0; d < 8; d++) {
14       static const int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
15       static const int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};
16       const int k = x + dx[d], l = y + dy[d];
17       if (0 <= k && k < 8 && 0 <= l && l < 8) {
18         dist[i][k*8+l] = 1;
19       }
20     }
21   }
22   for (int k = 0; k < 64; k++) {
23     for (int i = 0; i < 64; i++) {
24       for (int j = 0; j < 64; j++) {
25         dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
26       }
27     }
28   }
29 
30   string s;
31   cin >> s;
32   const int king = (s[0]-'A')*8 + s[1]-'1';
33   vector<int> knights;
34   for (string::size_type i = 2; i < s.size(); i += 2) {
35     knights.push_back((s[i]-'A')*8 + s[i+1]-'1');
36   }
37 
38   int ans = INF;
39   for (int i = 0; i < 64; i++) {
40     for (int j = 0; j < 64; j++) {
41       for (vector<int>::const_iterator it = knights.begin(); it != knights.end(); ++it) {
42         int a = abs(king/8 - i/8) + abs(king%8 - i%8) + dist[*it][i];
43         for (vector<int>::const_iterator jt = knights.begin(); jt != knights.end(); ++jt) {
44           a += jt == it ? dist[i][j] : dist[*jt][j];
45         }
46         ans = min(ans, a);
47       }
48     }
49   }
50   cout << ans << endl;
51   return 0;
52 }
poj/1178.cc