QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394574#7751. Palindrome PathAndy_LinWA 0ms3936kbC++142.5kb2024-04-20 16:20:192024-04-20 16:20:20

Judging History

你现在查看的是最新测评结果

  • [2024-04-20 16:20:20]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3936kb
  • [2024-04-20 16:20:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 32
#define pii pair<int,int>
#define ppp tuple<int,int,int,int>
int sr,sc,er,ec,n,m,a[N][N];
const short dd[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
char dy[5]="DRLU";
vector<int>ed;
namespace bl{
  bool flag[N][N];
  void dfs(int x,int y){
    flag[x][y]=1;
    for(int i=0;i<4;++i){
      int tx=x+dd[i][0],ty=y+dd[i][1];
      if(!a[tx][ty]||flag[tx][ty])continue;
      ed.push_back(i);
      dfs(tx,ty);
      ed.push_back(3-i);
    }
  }
}
namespace xy{
  bool flag[N][N][N][N];
  pair<ppp,int> pre[N][N][N][N];
  queue<ppp>q;
  pii solve(){
    flag[sr][sc][er][ec]=1;
    if(sr==er&&sc==ec){
      return {sr,sc};
    }
    q.push({sr,sc,er,ec});
    while(!q.empty()){
      int x,y,xx,yy;tie(x,y,xx,yy)=q.front();q.pop();
      for(int i=0;i<4;++i){
        int txx=xx+dd[3-i][0],tyy=yy+dd[3-i][1],tx=x,ty=y;
        if(a[x+dd[i][0]][y+dd[i][1]])tx+=dd[i][0],ty+=dd[i][1];
        if(!a[xx+dd[i][0]][yy+dd[i][1]]&&!flag[tx][ty][xx][yy]){
          flag[tx][ty][xx][yy]=1;
          pre[tx][ty][xx][yy]={{x,y,xx,yy},i};
          if(tx==xx&&ty==yy)return {tx,ty};
          q.push({tx,ty,xx,yy});
        }
        if(!a[xx+dd[3-i][0]][yy+dd[3-i][1]])continue;
        if(flag[tx][ty][txx][tyy])continue;
        flag[tx][ty][txx][tyy]=1;
        pre[tx][ty][txx][tyy]={{x,y,xx,yy},i};
        if(tx==txx&&ty==tyy)return {tx,ty};
        q.push({tx,ty,txx,tyy});
      }
    }
    return {0,0};
  }
}
vector<int>md;
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
      scanf("%1d",&a[i][j]);
    }
  }
  scanf("%d%d%d%d",&sr,&sc,&er,&ec);
  bl::dfs(er,ec);
  for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
      if(a[i][j]!=bl::flag[i][j]){
        puts("-1");return 0;
      }
    }
  }
  for(int i=ed.size()-1;i>=0;--i){
    putchar(dy[ed[i]]);
    int u=dd[ed[i]][0],v=dd[ed[i]][1];
    if(a[sr+u][sc+v])sr+=u,sc+=v;
  }
  int x,y,xx,yy;
  if(n!=2)return 0;
  tie(x,y)=xy::solve();xx=x,yy=y;
  while(make_tuple(x,y,xx,yy)!=make_tuple(sr,sc,er,ec)){
    int tx,ty,txx,tyy;
    tie(tx,ty,txx,tyy)=xy::pre[x][y][xx][yy].first;
    md.push_back(xy::pre[x][y][xx][yy].second);
    x=tx;y=ty;xx=txx;yy=tyy;
  }
  for(int i=md.size()-1;i>=0;--i){
    putchar(dy[md[i]]);
  }
  for(int i=0;i<md.size();++i){
    putchar(dy[md[i]]);
  }
  for(int i=0;i<ed.size();++i){
    putchar(dy[ed[i]]);
  }
  puts("");
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3720kb

input:

2 2
11
11
1 1 2 2

output:

RDLRULDRRDLURLDR

result:

ok Valid Solution (Length = 16).

Test #2:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

1 1
1
1 1 1 1

output:


result:

ok Valid Solution (Length = 0).

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3712kb

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

ULLDRDLDRRURDDLLLRRRUUUUDDLDLLURULURRD

result:

wrong answer Solution Not Palindrome