两天！终于AC了！

首先，很容易想到搜索，把步数用完，于是我先写了个深搜。

但也可想而知，即使不论对错，深搜在剪枝后还是超时了。

于是乎，我换成了广搜，答案错误，翻了下代码，毫无疑问，就是因为广搜在回来的时候会把经过糖果再次计算。

再想，我们又很容易发现，糖果只有 $18$ 个，我们可以给它们编号，而且要融进 $dis$ 数组，这样在回来时才好判断有没有经过，那么自然可以想到状态压缩。但是简单算一下就知道， $300 * 300 * 2^{18} \approx 2^{10}$ 这完全不可能开得出来。

不过，只有 $18$ 个糖果肯定有深意，沿着这个思路，给糖果编号是正确的，那么我们完全可以尝试状压 $dp$ 。这相当于，我们只在意关键节点，但是关键节点之间有距离，所以说我们需要求出每两两关键节点之间的最短距离。$Floyd$ $?$ 不，还是 $BFS$ 。

细化，我们继续展开状压 $dp$ 讲。状态是什么样的？每一个关键节点相当于二进制的某一位，即 $2$ 的某次幂，以代表某个糖果，记录当前状态下的最短步数。但是，当前状态被经过的节点那么多，怎么知道我现在在哪呢？所以说，我们需要再加一维，记录最终落在的关键节点。我们想到，$dp$ 应该从哪里开始呢，哦，当然从起点开始了，那起点也应该算进关键节点，那么最终落在的地方我们可以确定了，我直接让它最后落在终点岂不美哉？综上所述，形式地说：$dp_{mask,i}$ 表示当前状态是 $mask$ 最终落在 $i$ 关键节点（含起点终点）。那么转移就很简单了：$dp_{mask,i} = min(dp_{mask,i}, dp_{next,j} + dist_{i, j})$ 其中 $next$ 是下一个状态，$j$ 就是最终落在的关键节点。

你肯定还发现了，转移中出现了 $dist$ ，它就是之前提到的，两两之间的最短距离。这个用 $BFS$ 实现没什么好说的。

但是到这里的时候，也就是昨天，太晚了，只能含着遗憾与不甘入睡了，今天重拾，本来想着好难的，没想到写起来格外得心应手，所以我想说的其实就是——不难。

详情结合代码吧。

代码

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

int T = 1;
const int N = 300 + 10, MAXT = 2e6 + 10, K = 20;
const int M[] = {0, -1, 0, 1, 0};
int n, m, t;
char arr[N][N];
int start_x, start_y, end_x, end_y;

int cnt;
pair<int, int> candies[K];//记录糖果的坐标
int dist[K][K];//两两节点之间的距离
int dp[1 << K][K];//dp[mask][i]状态是mask，最终落在i上

int dis[N][N];
void Bfs(int idx) {
	int sx = candies[idx].first, sy = candies[idx].second;
	memset(dis, 127, sizeof(dis));
	dis[sx][sy] = 0;
	queue<pair<int, int>> q;
	q.push({sx, sy});
	
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if (dis[x][y] == t) continue;
		for (int i = 0; i < 4; i++) {
			int nx = x + M[i];
			int ny = y + M[i + 1];
			if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
			if (arr[nx][ny] == '#') continue;
			if (dis[nx][ny] > dis[x][y] + 1) {
				dis[nx][ny] = dis[x][y] + 1;
				q.push({nx, ny});
			}
		}
	}

	for (int i = 0; i < cnt; i++) {
		int x = candies[i].first;
		int y = candies[i].second;
		dist[idx][i] = dis[x][y];
		dist[i][idx] = dis[x][y];
	}
}

//这个不用看，用内置函数__builtin_popcount更快，用自己写的会超时[捂脸]
int CountBit(int num) {
	int cnt = 0;
	while (num) {
		cnt++;
		num ^= num & -num;//n&-n即lowbit取最右位的1，异或相同为0，也可以直接减
	}
	return cnt;
}

void Solve() {
	cin >> n >> m >> t;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'S') {
				start_x = i;
				start_y = j;
			}
			if (arr[i][j] == 'G') {
				end_x = i;
				end_y = j;
			}
		}
	}
	memset(dist, 127, sizeof(dist));
	//10..000..01最右边的1是起点，最左边的1是终点，中间的0是糖果
	candies[cnt].first = start_x, candies[cnt++].second = start_y;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (arr[i][j] == 'o') {
				candies[cnt].first = i;
				candies[cnt++].second = j;
			}
		}
	}
	candies[cnt].first = end_x, candies[cnt++].second = end_y;
	for (int i = 0; i < cnt - 1; i++) {//最后的终点不用再Bfs了，因为之前的已经包含了
		Bfs(i);
	}
	//时间复杂度：O(nmk)约是180000=1.8e5

	//状压dp
	memset(dp, 127, sizeof(dp));
	dp[1][0] = 0;//从起点开始
	int full = (1 << cnt) - 1;
	for (int mask = 1; mask <= full; mask += 2) {//因为开始位置是1，所以状态全是奇数
		for (int i = 0; i < cnt; i++) {//我现在待在这
			if (dp[mask][i] > 1e9) continue;//我首先要可能来到这里
			for (int j = 0; j < cnt; j++) {//我去这
				if (i == j) continue;
				if (dist[i][j] > 1e9) continue;//因为我们赋值的是127，一碰运算就炸
				int new_mask = mask | (1 << j);
				int res = min(dp[new_mask][j], dp[mask][i] + dist[i][j]);
				if (res <= t) dp[new_mask][j] = res;
			}
		}
	}
	//时间复杂度：O(2^k · k^2)约是4e8
	int ans = -1;
	for (int mask = 1 + (1 << (cnt - 1)); mask <= full; mask += 2) {//起点终点必须要到
		if (dp[mask][cnt - 1] <= t) {
			ans = max(ans, __builtin_popcount(mask) - 2ll);//去掉起点终点
		}
	}
	cout << ans;
	//总时间复杂度：O(nmk + 2^k · k^2)没超过5e8（5s）
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	while (T--) {
		Solve();
	}
	return 0;
}