5 sec, 1024 mb. 制約が 5 sec と長い．
大事な頂点の個数が少ない事を利用する． \(S, G, o\) が 20 個以下になるので，bit dp 可能． つまり，訪れた点の集合と時刻さえ分かれば，順番は関係ないということ．
実装: お菓子の置かれたマスの個数を \(c\) とする． お菓子のマスを \(0 , \cdots, c-1\), S のマスを \(c\) , G のマスを \(c+1\) とする．
前処理:
- BFSにより，大事なマス同士の距離を求めておく． 始点を大事なマスとする BFS で， \(O(\,(c+2)5HW\,)\).
- この結果を用いて，大事なマス同士のコストを求めておく．
後処理:
時刻が \(T\) 以下で辿り着けるマスのうち， \(x := \) (大事なマスを訪れた回数) \(- 2\) が最も多いものが答え． \(-2\) は，S,Gを除くため． \(x = pcntll(bitmsk)\) で求まる．
別解: 方針は同じだが，dp をするときに \( dp[bitmsk][vertex] = \{count, time\} \) の形で求める． \(time \leq T\) となる物だけ抽出しながら遷移する．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll h,w,t; cin >> h >> w >> t;
cinv(a);
ll c = 0;
map<pll, ll> id;
rep(i,h) rep(j,w){
if(a[i][j] == 'o') {
}
}
rep(i,h) rep(j,w){
if(a[i][j] == 'S') {
id[{i,j}] = c;
}
if(a[i][j] == 'G') {
id[{i,j}] = c+1;
}
}
ll n = c + 2;
vvll cost(n, vll(n, INFL));
// on original graph
{
auto bfs = [&](ll sx, ll sy) -> void {
vvll dis(h, vll(w, INFL));
queue<pll> que;
auto push = [&](ll x, ll y, ll d) -> void {
if(vis[x][y]) return;
vis[x][y] = true;
que.push({x,y});
chmin(dis[x][y], d);
if(id.find({x,y}) != id.end()){
chmin(cost[id[{sx,sy}]][id[{x,y}]], d);
}
};
push(sx, sy, 0);
while(que.size()){
auto [cx,cy] = que.front(); que.pop();
ll d = dis[cx][cy];
vll dx = {1,0,-1,0};
vll dy = {0,1,0,-1};
rep(i,4){
ll nx = cx + dx[i];
ll ny = cy + dy[i];
if(!in(nx,h)) continue;
if(!in(ny,w)) continue;
if(a[nx][ny] == '#') continue;
push(nx, ny, d + 1);
}
}
};
rep(x,h) rep(y,w) if(!(a[x][y] == '.' || a[x][y] == '#')){
bfs(x,y);
}
}
// on new graph
{
// dp : time
vvll dp(1LL<<n, vll(n, INFL));
dp[1LL<<c][c] = 0;
rep(s,(1LL<<n)) rep(cu, n) if(s >> cu & 1){
rep(ne, n) if(!(s >> ne & 1)){
ll ns = s | (1LL<<ne);
ll nt = dp[s][cu] + cost[cu][ne];
// if(nt <= t)
chmin(dp[ns][ne], nt);
}
}
ll ans = -INFL;
rep(s,(1LL<<n)) if(s >> (c+1) & 1){
if(dp[s][c+1] <= t)
chmax(ans, ll(pcntll(s)-2)); // 2 = {S,G}
}
if(ans < 0) ans = -1;
cout << ans << endl;
}
return 0;
}
