Submission

[PP][PPPPP]

Score: 100

User: Dormon

Problemset: Sirabyrinth 4

Language: cpp

Time: 0.002 second

Submitted On: 2024-12-03 09:34:51

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>

#define debug(...) Debug(#__VA_ARGS__, __VA_ARGS__)
using namespace std;

template<typename T>
typename std::enable_if<std::is_integral<T>::value>::type
Debug(const char* name, T value) {
    std::cout << name << " : " << value << '\n';
}

template<typename T, typename... Args>
typename std::enable_if<std::is_integral<T>::value>::type
Debug(const char* names, T value, Args... args) {
    const char* comma = strchr(names, ',');
    std::cout.write(names, comma - names) << " : " << value << " | ";
    Debug(comma + 1, args...);
}

vector<pair<int, int>> dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

struct A{
    int i, j, w;
};



void solve(){
    int n, m, mi, mj;
    cin >> n >> m;
    vector<string> grid(n+2);
    vector<vector<int>> distJ(n+2, vector<int>(m+2, 1e9));
    vector<vector<int>> distS(n+2, vector<int>(m+2, 1e9));

    queue<A> q;

    for (int i = 1;i <= n;i++){
        cin >> grid[i];
        grid[i] = '.' + grid[i] + '.';
        for (int j = 1;j <= m;j++)
            if (grid[i][j] == 'J')
                q.push({i, j, 0});
            else if (grid[i][j] == 'S')
                mi = i, mj = j;
    }

    auto invalid = [&](int i, int j) -> bool {
        return i < 1 || i > n || j < 1 || j > m;
    };

    auto printV = [&](vector<vector<int>> dist) -> void {
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= m;j++){
                if (dist[i][j] == 1e9) cout << "T ";
                else cout << dist[i][j] << ' '; 
            }
            cout << '\n';
        }
        cout << "==========\n";
    };

    while (!q.empty()){
        auto [i, j, w] = q.front(); q.pop();
        if (w >= distJ[i][j]) continue;
        distJ[i][j] = w;
        for (auto [di, dj]:dir){
            if (invalid(i+di, j+dj) || grid[i+di][j+dj] == '#') continue;
            q.push({i+di, j+dj, w+1});
        }
    }

    q.push({mi, mj, 0});

    while (!q.empty()){
        auto [i, j, w] = q.front(); q.pop();
        if (w >= distS[i][j] || w >= distJ[i][j]) continue;
        distS[i][j] = w;
        if (i == 1 || i == n || j == 1 || j == m){
            stack<char> ans;
            const int dirr[] = {-1, 0, 1, 0, -1};
            const string tid = "URDL";
            int ni = i, nj = j;
            while (ni != mi || nj != mj){
                //debug(ni, nj);
                for (int x = 0;x < 4;x++){
                    int ii = ni-dirr[x], jj = nj-dirr[x+1];
                    if (distS[ni][nj] == distS[ii][jj]+1){
                        ans.push(tid[x]);
                        ni = ii, nj = jj;
                        break;
                    }
                }
            }
            while (!ans.empty()){
                cout << ans.top();
                ans.pop();
            }
            cout << '\n';
            return ;
        }
        for (auto [di, dj]:dir){
            if (grid[i+di][j+dj] == '#') continue;
            q.push({i+di, j+dj, w+1});
        }
    }

    //printV(distJ);
    //printV(distS);

    cout << "I5\n";
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int q = 1; 
    //cin >> q;
    while (q--){
        solve();
    }
}