Submission

PPPPPPP

Score: 100

User: Monasm

Problemset: Sirabyrinth 4

Language: cpp

Time: 0.002 second

Submitted On: 2024-11-22 00:42:43

#include <bits/stdc++.h>

using namespace std;

int gx[] = {1,-1,0,0};
int gy[] = {0,0,1,-1};
string op = "DURL";

int main(){
    int n,m,px,py;cin>>n>>m;
    vector<vector<char>> adj(n,vector<char>(m));
    queue<pair<int,int>> q;
    vector<vector<int>> v1(n,vector<int>(m,1e9));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>adj[i][j];
            if(adj[i][j]=='S'){
                px=i;py=j;
            }
            else if(adj[i][j]=='J'){
                q.push({i,j});
            }
        }
    }
    int cnt = 0;
    while(!q.empty()){
        int size = q.size();
        for(int i=0;i<size;i++){
            int nx = q.front().first;
            int ny = q.front().second;
            if(v1[nx][ny]>cnt){
                v1[nx][ny]=cnt;
            }
            q.pop();
            for(int j=0;j<4;j++){
                int x=gx[j]+nx,y=gy[j]+ny;
                if(0<=x&&x<n&&0<=y&&y<m&&adj[x][y]!='#'&&v1[x][y]==1e9){
                    q.push({x,y});
                }
            }
        }
        cnt++;
    }
    q.push({px,py});cnt=0;
    int con=0;
    while(!q.empty()){
        int size = q.size();
        for(int i=0;i<size;i++){
            int nx = q.front().first;
            int ny = q.front().second;
            q.pop();
            if(nx==0||nx==n-1||ny==0||ny==m-1){
                con=1;px=nx;py=ny;break;
            }
            for(int j=0;j<4;j++){
                int x=gx[j]+nx,y=gy[j]+ny;
                if(0<=x&&x<n&&0<=y&&y<m&&adj[x][y]=='.'&&v1[x][y]>cnt+1){
                    adj[x][y]=op[j];
                    q.push({x,y});
                }
            }
        }
        cnt++;
    }
    if(con){
        string ans;
        char s = adj[px][py];
        while(s!='S'){
            ans+=s;
            for(int i=0;i<4;i++){
                if(s==op[i]){
                    px-=gx[i];py-=gy[i];break;
                }
            }
            s=adj[px][py];
        }
        reverse(ans.begin(),ans.end());
        cout<<ans;
    }
    else{
        cout<<"I5";
    }
}