提出 #74873834

---

ソースコード 拡げる

#include<bits/stdc++.h>

#define XAERIC666
// #define int long long
#define pii pair<int,int>
#define fi first
#define se second
#ifndef XAERIC666
  #define xaeric(...) {fprintf(stderr,__VA_ARGS__);fflush(stderr);}
#else
  #define xaeric(...) 114514
#endif
int read(){
  int x=0,f=1;
  char c=getchar();
  while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
  while('0'<=c&&c<='9'){x=x*10+c-48;c=getchar();}
  return x*f;
}
// void in(int*a,int n){for(int i=1;i<=n;i++)a[i]=read();}
// void out(int*a,int n){for(int i=1;i<=n;i++)printf("%lld%c",a[i]," \n"[i==n]);}
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _rep(i,a,b) for(int i=(b);i>=(a);--i)
#define YES puts("YES");
#define NO puts("NO");
void chmax(auto&a,auto b){if(a<b)a=b;}
void chmin(auto&a,auto b){if(a<b)a=b;}
using namespace std;

const int P=998244353;
const int N=1005;
const int NN=N*N*4,M=4*NN;
struct gph{
  int to[M],nx[M],hd[NN],t=1,w[M];
  void add(int u,int v,int k){
    to[++t]=v,nx[t]=hd[u],hd[u]=t,w[t]=k;
  }
}g;
int n,m,sy,sx,ey,ex;
char mp[N][N];
int dy[5]={1,0,-1,0};
int dx[5]={0,1,0,-1};
int fd[5]={2,3,0,1};
int hx(int y,int x,int l){
  return l*n*m+(y-1)*m+x;
}
int v[NN],lst[NN],pre[NN];
void solve(){
  n=read(),m=read();
  for(int i=1;i<=n;i++){
    scanf("%s",mp[i]+1);
    for(int j=1;j<=m;j++){
      if(mp[i][j]=='S'){
        sy=i;
        sx=j;
      }
      else if(mp[i][j]=='G'){
        ey=i;
        ex=j;
      }
    }
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      if(mp[i][j]=='#'){
        continue;
      }
      for(int k=0;k<4;k++){
        int ny=i+dy[k];
        int nx=j+dx[k];
        if(ny<1||ny>n){
          continue;
        }
        if(nx<1||nx>m){
          continue;
        }
        if(mp[ny][nx]=='#'){
          continue;
        }
        if(mp[i][j]=='.'||mp[i][j]=='S'){
          for(int l=0;l<4;l++){
            g.add(hx(i,j,l),hx(ny,nx,fd[k]),k);
          }
        }
        else if(mp[i][j]=='o'){
          g.add(hx(i,j,fd[k]),hx(ny,nx,fd[k]),k);
        }
        else if(mp[i][j]=='x'){
          for(int l=0;l<4;l++){
            if(l!=fd[k]){
              g.add(hx(i,j,l),hx(ny,nx,fd[k]),k);
            }
          }
        }
      }
    }
  }

  queue<int>q;
  q.push(hx(sy,sx,1));
  q.push(hx(sy,sx,2));
  q.push(hx(sy,sx,3));
  q.push(hx(sy,sx,0));
  v[hx(sy,sx,1)]=1;
  v[hx(sy,sx,2)]=1;
  v[hx(sy,sx,3)]=1;
  v[hx(sy,sx,0)]=1;
  while(q.size()){
    auto u=q.front();
    // xaeric(" %lld\n",u);
    q.pop();
    for(int i=g.hd[u];i;i=g.nx[i]){
      if(!v[g.to[i]]){
        q.push(g.to[i]);
        // xaeric("   ! %lld\n",g.to[i]);
        v[g.to[i]]=1;
        lst[g.to[i]]=g.w[i];
        pre[g.to[i]]=u;
      }
    }
  }
  int ans=0;
  if(v[hx(ey,ex,1)]){
    ans=hx(ey,ex,1);
  }
  if(v[hx(ey,ex,2)]){
    ans=hx(ey,ex,2);
  }
  if(v[hx(ey,ex,3)]){
    ans=hx(ey,ex,3);
  }
  if(v[hx(ey,ex,0)]){
    ans=hx(ey,ex,0);
  }
  if(!ans){
    puts("No");
    return;
  }
  puts("Yes");
  vector<int>aa;
  // aa.push_back();
  while(1){
    // xaeric(" %lld %lld\n",ans,pre[ans]);
    aa.push_back(lst[ans]);
    ans=pre[ans];
    if(ans==hx(sy,sx,1)){
      break;
    }
    if(ans==hx(sy,sx,2)){
      break;
    }
    if(ans==hx(sy,sx,3)){
      break;
    }
    if(ans==hx(sy,sx,0)){
      break;
    }
  }
  // xaeric("%lld %lld %lld %lld",hx(sy,sx,0),hx(sy,sx,1),hx(sy,sx,2),hx(sy,sx,3));
  reverse(aa.begin(),aa.end());
  for(auto i:aa){
    if(i==0){
      printf("D");
    }
    else if(i==1){
      printf("R");
    }
    else if(i==2){
      printf("U");
    }
    else{
      printf("L");
    }
  }
  puts("");
}

signed main(){
  int TTTT=1;
  // int TTTT=read();
  while(TTTT--){
    solve();
  }
}

提出情報

ジャッジ結果