提出 #74868818

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,char> pic;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef priority_queue<int,vi,greater<int>> mipqint;
typedef priority_queue<int> pqint;
#define SZ(x) ((int)x.size())
const int mod = 1e9+7;
const int P = 998244353;
const int md = 101;
const ll inf = (1LL << 60LL);
const int N = 2e5+10;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const char dc[] = "UDLR";
struct Node {
    int x, y, d;
};
struct Pre {
    int x, y, d;
    char c;
} pre[1005][1005][5];
bool vis[1005][1005][5];
char s[1005][1005];
int H, W;
int sx, sy, gx, gy;
bool in(int x, int y) {
    return x >= 0 && x < H && y >= 0 && y < W;
}
int main() {
    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        cin >> s[i];
        for (int j = 0; j < W; j++) {
            if (s[i][j] == 'S') sx = i, sy = j;
            if (s[i][j] == 'G') gx = i, gy = j;
        }
    }
    memset(vis, 0, sizeof(vis));
    queue<Node> q;
    q.push({sx, sy, 4});
    vis[sx][sy][4] = 1;
    int found = -1;
    while (!q.empty()) {
        auto [x, y, d] = q.front();
        q.pop();

        if (x == gx && y == gy) {
            found = d;
            break;
        }
        for (int to = 0; to < 4; to++) {
            int nx = x + dx[to];
            int ny = y + dy[to];
            if (!in(nx, ny) || s[nx][ny] == '#') continue;
            bool ok = 1;
            if (d != 4) {
                if (s[x][y] == 'o') {
                    if (to != d) ok = 0;
                } else if (s[x][y] == 'x') {
                    if (to == d) ok = 0;
                }
            }

            if (!ok) continue;
            if (vis[nx][ny][to]) continue;

            vis[nx][ny][to] = 1;
            pre[nx][ny][to] = {x, y, d, dc[to]};
            q.push({nx, ny, to});
        }
    }

    if (found == -1) {
        cout << "No\n";
        return 0;
    }
    string path;
    int x = gx, y = gy, d = found;
    while (!(x == sx && y == sy)) {
        auto p = pre[x][y][d];
        path += p.c;
        x = p.x;
        y = p.y;
        d = p.d;
    }
    reverse(path.begin(), path.end());

    cout << "Yes\n" << path << '\n';
    return 0;
}

提出情報

ジャッジ結果