PKU 2688 Cleaning Robot

• 幅優先探索
• 及び全探索
• 以下のコードはPKUではTLE

static const int dx[] = {0, 0, 1, -1};
static const int dy[] = {1, -1, 0, 0};

int main() {
	for (int w, h; cin >> w >> h && (w || h); ) {
		char maze[32][32];
		memset(maze, 'x', sizeof(maze));

		vector<pair<int, int> > points(1);

		for (int y = 1; y <= h; ++y) {
			for (int x = 1; x <= w; ++x) {
				char c;
				cin >> c;
				maze[x][y] = c;

				if (c == 'o') {
					points[0] = make_pair(x, y);
				} else if (c == '*') {
					points.push_back(make_pair(x, y));
				}
			}
		}

		int cost[16][16];
		REP(start, points.size()) {
			const int startX = points[start].first;
			const int startY = points[start].second;

			int dp[32][32];
			fill_n((int*)dp, sizeof(dp) / sizeof(int), INT_MAX / 3);
			dp[startX][startY] = 0;

			queue<int> q;
			q.push(startX);
			q.push(startY);

			while (!q.empty()) {
				const int x = q.front();
				q.pop();
				const int y = q.front();
				q.pop();

				REP(dir, 4) {
					const int xx = x + dx[dir];
					const int yy = y + dy[dir];

					if (maze[xx][yy] == 'x') {
						continue;
					}

					if (dp[xx][yy] > dp[x][y] + 1) {
						dp[xx][yy] = dp[x][y] + 1;
						q.push(xx);
						q.push(yy);
					}
				}
			}

			REP(goal, points.size()) {
				cost[start][goal] = dp[points[goal].first][points[goal].second];
			}
		}

		vector<int> p;
		for (int i = 1; i < points.size(); ++i) {
			p.push_back(i);
		}

		int bestAnswer = INT_MAX;
		do {
			int answer = 0;
			answer = cost[0][p.front()];
			answer = min(answer, INT_MAX / 3);
			REP(i, p.size() - 1) {
				answer += cost[p[i]][p[i + 1]];
				answer = min(answer, INT_MAX / 3);
			}

			bestAnswer = min(bestAnswer, answer);

		} while (next_permutation(ALL(p)));

		if (bestAnswer == INT_MAX / 3) {
			bestAnswer = -1;
		}

		cout << bestAnswer << endl;
	}
}