Submission

[PP][PPPPP]

Score: 100

User: Nathlol2

Problemset: Sirabyrinth 4

Language: cpp

Time: 0.002 second

Submitted On: 2025-01-04 18:28:14

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

int n, m;
vector<pair<int, int>> mon;
vector<vector<int>> g; // To store monster times
map<pair<int, int>, pair<int, int>> parent;
int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};
char dir[4] = {'R', 'L', 'D', 'U'};
int sx, sy, ex, ey;
vector<string> str;

bool valid(int x, int y, int t) {
    if (x < 0 || x >= n || y < 0 || y >= m) return false;
    if (str[x][y] == '#' || t >= g[x][y]) return false;
    return true;
}

bool isEdge(int x, int y, int t) {
    if (!valid(x, y, t)) return false;
    if (x == 0 || y == 0 || x == n - 1 || y == m - 1) return true;
    return false;
}

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

    cin >> n >> m;
    str.resize(n);
    g.assign(n, vector<int>(m, INT_MAX));

    for (int i = 0; i < n; i++) {
        cin >> str[i];
        for (int j = 0; j < m; j++) {
            if (str[i][j] == 'J') {
                mon.pb({i, j});
            }
            if (str[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }
	if(isEdge(sx, sy, 0)){
		cout << "YES\n0";
		exit(0);
	}
    queue<pair<pair<int, int>, int>> q;
    for (auto i : mon) {
        q.push({i, 0});
        g[i.first][i.second] = 0;
    }
    while (!q.empty()) {
        auto [cx, cy] = q.front().first;
        int t = q.front().second;
        q.pop();
        t++;
        for (int mv = 0; mv < 4; mv++) {
            int x = cx + mx[mv];
            int y = cy + my[mv];
            if (valid(x, y, t)) {
                g[x][y] = t;
                q.push({{x, y}, t});
            }
        }
    }
    queue<pair<pair<int, int>, int>> qq;
    qq.push({{sx, sy}, 0});
    parent[{sx, sy}] = {-1, -1};
    bool found = false;
    while (!qq.empty() && !found) {
        auto [cx, cy] = qq.front().first;
        int t = qq.front().second;
        qq.pop();
        t++;
        for (int mv = 0; mv < 4 && !found; mv++) {
            int x = cx + mx[mv];
            int y = cy + my[mv];
            if (isEdge(x, y, t)) {
                parent[{x, y}] = {cx, cy};
                ex = x; ey = y;
                found = true;
            }
            if (valid(x, y, t)) {
                parent[{x, y}] = {cx, cy};
                str[x][y] = '#'; // Mark as visited
                qq.push({{x, y}, t});
            }
        }
    }

    if (!found) {
        cout << "I5";
        exit(0);
    }
    string path = "";
    pair<int, int> cur = {ex, ey};
    while (cur != make_pair(sx, sy)) {
        pair<int, int> prev = parent[cur];
        int dx = cur.first - prev.first;
        int dy = cur.second - prev.second;

        for (int i = 0; i < 4; i++) {
            if (dx == mx[i] && dy == my[i]) {
                path += dir[i];
                break;
            }
        }
        cur = prev;
    }
    reverse(path.begin(), path.end());
    cout << path << '\n';
}