AOJ 2284 - The Legendary Sword

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2284

解法

コンテスト中，「1の宝珠をすべてとってから2の宝珠をとる」と勘違いしていて解けなかった．

1の宝珠を1つでもとれば2の宝珠をとりにいけるので DP．

 1 #include <iostream>
 2 #include <sstream>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9   int W, H;
10   while (cin >> W >> H && W != 0) {
11     static vector<pair<int,int> > ps[3000];
12     for (int i = 0; i < 3000; i++) {
13       ps[i].clear();
14     }
15     pair<int,int> g;
16     int m = 0;
17     for (int i = 0; i < H; i++) {
18       for (int j = 0; j < W; j++) {
19         string s;
20         cin >> s;
21         istringstream iss(s);
22         int n;
23         if (s == "S") {
24           ps[0].push_back(make_pair(i, j));
25         } else if (s == "G") {
26           g = make_pair(i, j);
27         } else if (iss >> n) {
28           ps[n].push_back(make_pair(i, j));
29           m = max(m, n);
30         }
31       }
32     }
33     ps[++m].push_back(g);
34 
35     static int dp[3000][3000];
36     for (int i = 1; i <= m; i++) {
37       fill_n(dp[i], ps[i].size(), 10000000);
38       for (int j = 0; j < ps[i-1].size(); j++) {
39         for (int k = 0; k < ps[i].size(); k++) {
40           const int l = abs(ps[i][k].first - ps[i-1][j].first) + abs(ps[i][k].second - ps[i-1][j].second);
41           dp[i][k] = min(dp[i][k], dp[i-1][j] + l);
42         }
43       }
44     }
45     cout << dp[m][0] << endl;
46   }
47   return 0;
48 }