这道题一眼望上去看起来是最短路或者广搜，但是 $k\le 2\times 10^6$，让你没法下手。
不过发现有糖果的格子最多只有 $18$ 个，加上起点终点只有 $20$ 个点有用，那么什么样的题目数据范围是 $20$ 呢？
不难算出 $2^{20}$ 大概是一百万，于是就想到了状压DP。
定义 $f[i][j]$ 表示当前点为 $i$，状态为 $j$ 时的最短距离。定义 $d[i][j]$ 表示点 $i$ 到 $j$ 的距离，如果不连通则 $d[i][j]=\infty$。
先用广搜算出所有有用的点（不妨设是 $t$ 个）两两之间的距离，然后枚举下一个走的点 $k$，可以得到：
$f[i][j]=\min(f[i][j],f[k][j-2^k]+d[i][k])$
那么对于距离不超过要求的状态，求最大数量的 $1$ 即可，可以使用 lowbit 每次砍掉一位计算。
时间复杂度 $O(t^2\times 2^t)$。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e2 + 5, MR = 1e4 + 5, MN = 21, MM = 1 << 19;
int n, m, l, ans, sx, sy, ex, ey, num, mp[MAXN][MAXN], used[MAXN][MAXN], g[MN][MN], f[MN][MM];
char ch[MAXN][MAXN];
struct node{
int x, y;
}d[MAXN];
struct step{
int x, y, st;
};
int lowbit(int x){return x & -x;}
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
void bfs(int p, int q){
queue<step>pq;
pq.push({p, q, 0});
memset(used, 0, sizeof(used));
used[p][q] = 1;
while(!pq.empty()){
int hx = pq.front().x, hy = pq.front().y, hst = pq.front().st;
pq.pop();
for(int i = 0;i < 4;i ++){
int tx = hx + dx[i], ty = hy + dy[i];
if(used[tx][ty] || tx <= 0 || ty <= 0 || tx > n || ty > m || ch[tx][ty] == '#')continue;
used[tx][ty] = 1;
if(mp[tx][ty])g[mp[p][q]][mp[tx][ty]] = g[mp[tx][ty]][mp[p][q]] = hst + 1;
pq.push({tx, ty, hst + 1});
}
}
}
int main(){
scanf("%d%d%d", &n, &m, &l);
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
cin >> ch[i][j];
if(ch[i][j] == 'S')sx = i, sy = j, mp[i][j] = ++ num, d[num] = {i, j};
if(ch[i][j] == 'G')ex = i, ey = j, mp[i][j] = ++ num, d[num] = {i, j};
if(ch[i][j] == 'o')mp[i][j] = ++ num, d[num] = {i, j};
}
}
int ppp = mp[sx][sy];
swap(mp[sx][sy], mp[d[num - 1].x][d[num - 1].y]);
swap(d[num - 1], d[ppp]);
ppp = mp[ex][ey];
swap(mp[ex][ey], mp[d[num].x][d[num].y]);
swap(d[num], d[ppp]);
for(int i = 1;i <= num;i ++){
bfs(d[i].x, d[i].y);
for(int j = 1;j <= num;j ++){
if(!used[d[j].x][d[j].y])g[i][j] = g[j][i] = 1e9;
}
}
if(g[num - 1][num] > l){
puts("-1");
return 0;
}
memset(f, 0x3f, sizeof(f));
for(int i = 1;i <= num - 2;i ++)f[i][1 << i] = g[i][num - 1];
for(int k = 0;k < (1 << num - 1) - 1;k ++){
for(int i = 1;i <= num - 2;i ++){
if((1 << i) & k){
for(int j = 1;j <= num - 2;j ++){
if(i == j || (1 << j) & k)continue;
f[j][k | (1 << j)] = min(f[j][k | (1 << j)], f[i][k] + g[i][j]);
}
}
}
}
for(int i = 1;i <= num - 2;i ++){
for(int k = 0;k < (1 << num - 1) - 1;k ++){
if(k & (1 << i)){
if(f[i][k] + g[i][num] <= l){
int res = 0, pp = k;
while(pp){
res ++;
pp -= lowbit(pp);
}
// printf("%d %d %d\n", k, res, f[i][k] + g[i][num]);
ans = max(ans, res);
}
}
}
}
printf("%d", ans);
return 0;
}