POJ 2688 - Cleaning Robot

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

概要，制約

日本語の問題文を参照． Problem F: Cleaning Robot

解法

各点同士の最短経路を求めてから巡回セールスマン問題として解く．

TLE が厳しめな気がする．

 1 #include <cstdio>
 2 #include <queue>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int H, W;
 7 char grid[20][20];
 8 
 9 int bfs(const pair<int,int>& start, const pair<int,int>& goal)
10 {
11   queue<pair<pair<int,int>,int> > q;
12   q.push(make_pair(start, 0));
13   static bool visited[20][20];
14   for (int i = 0; i < H; i++) {
15     fill_n(visited[i], W, false);
16   }
17   visited[start.first][start.second] = true;
18   while (!q.empty()) {
19     const pair<pair<int,int>,int> p = q.front();
20     q.pop();
21     if (p.first == goal) {
22       return p.second;
23     }
24 
25     for (int d = 0; d < 4; d++) {
26       static const int dir_i[] = {0, 0, -1, 1};
27       static const int dir_j[] = {-1, 1, 0, 0};
28       const int i = p.first.first + dir_i[d];
29       const int j = p.first.second + dir_j[d];
30       if (0 <= i && i < H && 0 <= j && j < W && !visited[i][j] && grid[i][j] != 'x') {
31         visited[i][j] = true;
32         q.push(make_pair(make_pair(i, j), p.second+1));
33       }
34     }
35   }
36   return 1000000;
37 }
38 
39 int main()
40 {
41   while (scanf("%d %d", &W, &H) == 2 && W != 0) {
42     pair<int,int> nodes[11];
43     int N = 0;
44     pair<int,int> robot;
45     for (int i = 0; i < H; i++) {
46       scanf("%s", grid[i]);
47       for (int j = 0; j < W; j++) {
48         if (grid[i][j] == '*') {
49           nodes[N].first = i;
50           nodes[N].second = j;
51           ++N;
52         } else if (grid[i][j] == 'o') {
53           robot.first = i;
54           robot.second = j;
55         }
56       }
57     }
58 
59     nodes[N++] = robot;
60     static int weights[11][11];
61     for (int i = 0; i < N; i++) {
62       fill_n(weights[i], N, 0);
63     }
64     for (int i = 0; i < N; i++) {
65       for (int j = i+1; j < N; j++) {
66         weights[i][j] = weights[j][i] = bfs(nodes[i], nodes[j]);
67       }
68     }
69 
70     static int dp[1<<11][11];
71     for (int s = 0; s < (1<<N); s++) {
72       fill_n(dp[s], N, 1000000);
73     }
74     for (int i = 0; i < N; i++) {
75       dp[1<<i][i] = weights[N-1][i];
76     }
77     for (int s = 0; s < (1<<N); s++) {
78       for (int i = 0; i < N; i++) {
79         if ((s & (1<<i)) == 0) { continue; }
80         for (int j = 0; j < N; j++) {
81           if ((s & (1<<j)) != 0) { continue; }
82           const int t = s | (1<<j);
83           dp[t][j] = min(dp[t][j], dp[s][i] + weights[i][j]);
84         }
85       }
86     }
87 
88     int ans = 1000000;
89     for (int i = 0; i < N-1; i++) {
90       ans = min(ans, dp[((1<<N)-1)][i]);
91     }
92     if (ans >= 1000000) {
93       puts("-1");
94     } else {
95       printf("%d\n", ans);
96     }
97   }
98   return 0;
99 }