Submission

PPPxPxx

Score: 60

User: tull

Problemset: Sirabyrinth 1

Language: cpp

Time: 0.103 second

Submitted On: 2025-04-12 05:26:00

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ll long long
template <class T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
using pil=pair<int,long long>;
using pli=pair<long long,int>;
using pll=pair<long long,long long>;
using pii=pair<int,int>;
using piii=pair<pair<int,int>,int>;
using plll=pair<pair<ll,ll>,ll>;
using pic=pair<int,char>;
const int MX= 1000000000000000000LL; //1e18
const int MN=-MX; //-1e18
const int MOD = 1e9+7;
#define bp '\n'
#define ull unsigned long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define inv(a) for(auto&e:a){cin>>e;}
#define vp cout<<'\n';
#define inv2dm(a) for(auto&e:a)for(auto&c:e)cin>>c;
#define ck(a) for(auto&e:a)cout<<e<<' ';cout<<'\n';
#define ckpf(a) for(auto&e:a)printf("%d ",e);printf("\n");
#define ckpair(a) for(auto&[f,s]:a)cout<<"("<<f<<", "<<s<<") ";cout<<'\n';
#define LMX LLONG_MAX
#define LMN LLONG_MIN
#define ck2dm(a) cout<<'\n';for(auto&e:a){for(auto&c:e)cout<<((c==MX or c==MN)?9:c)<<' ';cout<<'\n';}
#define ck2dmlr(a,l,r) cout<<'\n';for(int i=0;i<l;++i){for(int j=0;j<r;++j){cout<<((a[i][j]==MN or a[i][j]==MX)?9:a[i][j])<<'\t';}cout<<'\n';}
#define tostr(a) to_string(a)
#define qs(a) for(int i=1;i<a.size();++i)a[i]+=a[i-1];
#define vpii vector<pair<int,int>>
#define dir vector<pair<int,int>>direct={{-1,0},{1,0},{0,1},{0,-1}};
#define val(i,j) (i>=0 and i<n and j>=0 and j<m)?1:0
#define vi vector<int>
#define mt make_tuple
#define mp make_pair
#define db double
dir
signed main(){
    //freopen("test_input.txt","r",stdin);
    cin.tie(NULL)->sync_with_stdio(false);
    int n,m,si,sj;
    cin>>n>>m;
    vector<string>a(n);
    queue<tuple<int,int,string>>q;
    for(int i=0;i<n;++i){
        cin>>a[i];
        for(int j=0;j<m;++j){
            if(a[i][j]=='S')si=i,sj=j;
        }
    }
    q.emplace(si,sj,"");
    while(!q.empty()){
        auto [i,j,pp]=q.front();
        //cout<<pp<<':'<<i<<' '<<j<<bp;
        q.pop();
        if(i==0 or i==n-1 or j==0 or j==m-1){
            //cout<<i<<' '<<j<<bp;
            cout<<pp.size()<<bp<<pp;
            return 0;
        }
        for(auto&[f,s]:direct){
            int o=f+i,p=s+j;
            if(val(o,p)){
                if(a[o][p]=='#')
                    continue;
                char c;
                if(f==1){
                    c='D';
                }
                if(f==-1){
                    c='U';
                }
                if(s==1){
                    c='R';
                }
                if(s==-1){
                    c='L';
                }
                q.push(mt(o,p,pp+c));
            }
        }
    }
    return 0;
}