ABC301 E問題（Pac-Takahashi）を解く

#include <bits/stdc++.h>
using namespace std;

#define INF (1 << 30)

int h, w;
vector<string> a;
int di[4] = {1, 0, -1,  0};
int dj[4] = {0, 1,  0, -1};

vector<vector<int>> bfs(int i, int j)
{
	vector<vector<int>> dist(h, vector<int>(w, -1));
	queue<pair<int, int>> que;

	que.push(make_pair(i, j));
	dist[i][j] = 0;
	while (!que.empty()) {
		auto now = que.front();
		que.pop();
		int now_i = now.first;
		int now_j = now.second;

		for (int d = 0; d < 4; ++d) {
			int next_i = now_i + di[d];
			int next_j = now_j + dj[d];
			if ((0 <= next_i)&&(next_i < h)
			  &&(0 <= next_j)&&(next_j < w)
			  &&(dist[next_i][next_j] == -1)
			  &&(a[next_i][next_j] != '#')) {
				que.push(make_pair(next_i, next_j));
				dist[next_i][next_j] = dist[now_i][now_j] + 1;
			}
		}
	}

	return dist;
}

int main()
{
	int t;
	cin >> h >> w >> t;
	a.resize(h);
	for (int i = 0; i < h; ++i) {
		cin >> a[i];
	}

	int si, sj;
	int gi, gj;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			if (a[i][j] == 'S') {
				si = i;
				sj = j;
			}
			if (a[i][j] == 'G') {
				gi = i;
				gj = j;
			}
		}
	}

	vector<pair<int, int>> i2p;
	i2p.push_back(make_pair(si, sj));
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			if (a[i][j] == 'o') {
				i2p.push_back(make_pair(i, j));
			}
		}
	}
	i2p.push_back(make_pair(gi, gj));

	int n = i2p.size();
	vector<vector<int>> dist(n, vector<int>(n, INF));
	for (int i = 0; i < n; ++i) {
		vector<vector<int>> d = bfs(i2p[i].first, i2p[i].second);
		for (int j = 0; j < n; ++j) {
			if (d[i2p[j].first][i2p[j].second] != -1) {
				dist[i][j] = d[i2p[j].first][i2p[j].second];
			}
		}
	}

	vector<vector<int>> dp(1 << n, vector<int>(n, INF));
	dp[1][0] = 0;
	for (int i = 1; i < (1 << n); ++i) {
		for (int j = 0; j < n; ++j) {
			if ((i & (1 << j)) == 0) {
				continue;
			}
			if (dp[i][j] == INF) {
				continue;
			}
			for (int k = 1; k < n; ++k) {
				if (dist[j][k] == INF) {
					continue;
				}
				if ((i & (1 << k)) == 0) {
					int v = (i | (1 << k));
					dp[v][k] = min(dp[v][k], dp[i][j] + dist[j][k]);
				}
			}
		}
	}

	int result;
	if ((dist[0][n - 1] <= t)) {
		result = 0;
	} else {
		cout << -1 << endl;
		return 0;
	}
	for (int i = 1; i < (1 << n); ++i) {
		if (((i & 1) != 0)&&(dp[i][n - 1]  <= t)) {
			result = max(result, __builtin_popcount(i) - 2);
		}
	}
	cout << result << endl;

	return 0;
}