提出 #41381678

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define test int T; cin >> T; while(T--)
using namespace std;
using lnt = long long;

int h, w, t, sx, sy, gx, gy, dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int vst[307][307];
int a[307][307];
int ans = -1;

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int cnt = 0;
    memset(vst, -1, sizeof(vst));
    cin >> h >> w >> t;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            char c;
            cin >> c;
            if(c == 'S') sx = i, sy = j;
            if(c == 'G') gx = i, gy = j;
            if(c == '#') a[i][j] = -1;
            if(c == 'o') a[i][j] = ++cnt;
        }
    }
    queue<tuple<int, int, int, int>> q;
    q.push({sx, sy, 0, 0});
    vst[sx][sy] = 0;
    while(!q.empty()){
        auto [x, y, nc, l] = q.front();
        q.pop();
        if(l > t) break;
        if(x == gx && y == gy){
            ans = max(ans, __builtin_popcount(nc));
        }
        for(int i=0; i<4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(!nx || !ny || nx > h || ny > w) continue;
            if(a[nx][ny] == -1) continue;
            int nnc = a[nx][ny] > 0 ? (nc | (1 << a[nx][ny])) : nc;
            if(vst[nx][ny] != -1 && __builtin_popcount(vst[nx][ny]) >= __builtin_popcount(nnc)) continue;
            vst[nx][ny] = nnc;
            q.push({nx, ny, nnc, l+1});
        }
    }
    cout << ans;
}

提出情報

ジャッジ結果