Submission #74878294

---

Source Code Expand

#include<bits/stdc++.h>
// #include<atcoder/all>
using namespace std;
using ll = long long;
#define rep(i, n) for(int  i = 0; i < (n); ++i)
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const long long INF = 1LL << 60;
using Graph = vector<vector<int>>;
int gcd(int a, int b){
    if(b == 0) return a;  
    else return gcd(b, a%b);
}
struct Compare {
    bool operator()(const pair<ll, int>& a, const pair<ll, int>& b) {
        return a.first > b.first;  
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h,w; cin >> h >> w;
    vector<vector<char>> s(h, vector<char>(w));
    int sx,sy,gx,gy;
    rep(i,h){
        rep(j,w){
            cin >> s[i][j];
            if(s[i][j] == 'S'){
                sx = i, sy = j;
            }
            if(s[i][j] == 'G'){
                gx = i, gy = j;
            }
        }
    }
    vector<int> dx = {-1,0,1,0}, dy = {0,1,0,-1};
    vector<vector<vector<ll>>> dp(h, vector<vector<ll>>(w, vector<ll>(4, INF)));
    rep(i,4) dp[sx][sy][i] = 0;
    auto valid = [&](int x, int y){
        if(x < 0 || x >= h || y<0 || y>=w) return false;
        return true;
    };
    priority_queue<tuple<ll, int,int,int>, vector<tuple<ll,int,int,int>>, greater<tuple<ll,int,int,int>>> pq;
    rep(i,4) pq.push(make_tuple(0LL, sx,sy,i));
    while(!pq.empty()){
        auto [dist, x, y, dir] = pq.top();
        pq.pop();
        if(dist > dp[x][y][dir]) continue;
        if(dist > 5000000) continue;
        if(s[x][y] == 'o'){
            int nx = x+dx[dir],ny = y+dy[dir];
            if(!valid(nx, ny)) continue;
            if(s[nx][ny] == '#') continue;
            if(chmin(dp[nx][ny][dir], dist+1)){
                if(s[nx][ny] == 'G') continue;
                pq.push(make_tuple(dp[nx][ny][dir], nx, ny, dir));
            }
        }else{
            rep(i,4){
                if(s[x][y] == 'x' && dir == i) continue;
                int nx = x + dx[i], ny = y+dy[i];
                if(!valid(nx, ny)) continue;
                if(s[nx][ny] == '#') continue;
                if(chmin(dp[nx][ny][i], dist+1)){
                    if(s[nx][ny] == 'G') continue;
                    pq.push(make_tuple(dp[nx][ny][i], nx, ny, i)); 
                }
            }
        }
    }
    bool ok = false;
    rep(i,4){
        if(dp[gx][gy][i] <= 5000000) ok = true;
    }
    vector<char> di = {'U', 'R', 'D', 'L'};
    // rep(i,h){
    //   rep(j,w){
    //     rep(k,4){
    //       cout << dp[i][j][k];
    //     }
    //     cout <<" ";
    //   }
    //   cout << endl;
    // }
    if(ok){
        cout << "Yes\n";
        ll now_dist = INF;
        int now_dir = 0;
        rep(i,4){
            if(chmin(now_dist, dp[gx][gy][i])){
                now_dir = i;
            }
        }
        int npx = gx, npy = gy;
        vector<char> ans;
        while(1){
            if(s[npx][npy] == 'S') break;
            int nx = npx - dx[now_dir], ny = npy - dy[now_dir];
            ans.push_back(di[now_dir]);
            if(s[nx][ny] == 'o'){
                npx = nx;
                npy = ny;
                now_dist--;
            }else{
                rep(i,4){
                    if(s[nx][ny] == 'x' && i == now_dir) continue;
                    if(dp[nx][ny][i] == now_dist - 1){
                        now_dir = i;
                        now_dist--;
                        npx = nx;
                        npy = ny;
                        break;
                    }
                }
            }
        }
        reverse(ans.begin(), ans.end());
        for(auto c:ans){
            cout << c;
        }
    }else{
        cout << "No\n";
    }
}

Submission Info

Compile Error

./Main.cpp: In function 'main':
./Main.cpp:74:17: warning: 'gx' may be used uninitialized [-Wmaybe-uninitialized]
   74 |         if(dp[gx][gy][i] <= 5000000) ok = true;
      |                 ^
./Main.cpp:25:15: note: 'gx' was declared here
   25 |     int sx,sy,gx,gy;
      |               ^
./Main.cpp:74:21: warning: 'gy' may be used uninitialized [-Wmaybe-uninitialized]
   74 |         if(dp[gx][gy][i] <= 5000000) ok = true;
      |                     ^
./Main.cpp:25:18: note: 'gy' was declared here
   25 |     int sx,sy,gx,gy;
      |                  ^
./Main.cpp:39:19: warning: 'sx' may be used uninitialized [-Wmaybe-uninitialized]
   39 |     rep(i,4) dp[sx][sy][i] = 0;
      |                   ^
./Main.cpp:25:9: note: 'sx' was declared here
   25 |     int sx,sy,gx,gy;
      |         ^
./Main.cpp:39:23: warning: 'sy' may be used uninitialized [-Wmaybe-uninitialized]
   39 |     rep(i,4) dp[sx][sy][i] = 0;
      |                       ^
./Main.cpp:25:12: note: 'sy' was declared here
   25 |     int sx,sy,gx,gy;
      |            ^

Judge Result