QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352675#7751. Palindrome PathGraphcityWA 0ms3956kbC++202.3kb2024-03-13 15:03:252024-03-13 15:03:25

Judging History

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

  • [2024-03-13 15:03:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3956kb
  • [2024-03-13 15:03:25]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=30;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

int n,m,ch[35][35],sx,sy,tx,ty;
int vis[35][35]; pair<int,int> pr[35][35];
vector<char> ans;

inline int chk(int x,int y)
{return (x>=1 && x<=n && y>=1 && y<=m && ch[x][y]==1);}
inline void bfs()
{
    queue<pair<int,int>> q;
    vis[tx][ty]=1,q.emplace(tx,ty);
    while(!q.empty())
    {
        auto [x,y]=q.front(); q.pop();
        For(_,0,3)
        {
            int x1=x+dx[_],y1=y+dy[_];
            if(!chk(x1,y1) || vis[x1][y1]) continue;
            vis[x1][y1]=1,pr[x1][y1]=make_pair(x,y),q.emplace(x1,y1);
        }
    }
}
inline void MR(int op)
{
    int x1=sx,y1=sy,x2=tx,y2=ty,cnt=0;
    while(chk(x1,y1-op) && chk(x2,y2+op)) ans.push_back(op==1?'L':'R'),y1-=op,y2+=op,cnt++;
    if(!chk(x2,y2+op)) {For(i,1,cnt+1) ans.push_back(op==1?'R':'L');}
    else {ans.push_back(op==1?'L':'R'); For(i,1,cnt+1) ans.push_back(op==1?'R':'L');}
}
inline void MD(int op)
{
    int x1=sx,y1=sy,x2=tx,y2=ty,cnt=0;
    while(chk(x1-op,y1) && chk(x2+op,y2)) ans.push_back(op==1?'U':'D'),x1-=op,x2+=op,cnt++;
    if(!chk(x2+op,y2)) {For(i,1,cnt+1) ans.push_back(op==1?'D':'U');}
    else {ans.push_back(op==1?'U':'D'); For(i,1,cnt+1) ans.push_back(op==1?'D':'U');}
}
inline void dfs(int x,int y)
{
    vis[x][y]=1;
    For(_,0,3)
    {
        int x1=x+dx[_],y1=y+dy[_];
        if(!chk(x1,y1) || vis[x1][y1]) continue;
        if(x1==x+1) MD(1); if(x1==x-1) MD(-1);
        if(y1==y+1) MR(1); if(y1==y-1) MR(-1);
        dfs(x1,y1);
        if(x1==x+1) MD(-1); if(x1==x-1) MD(1);
        if(y1==y+1) MR(-1); if(y1==y-1) MR(1);
    }
}

int main()
{
    // freopen("1.in","r",stdin);

    cin>>n>>m;
    For(i,1,n) For(j,1,m) scanf("%1d",&ch[i][j]);
    cin>>sx>>sy>>tx>>ty; bfs();
    For(i,1,n) For(j,1,m) if(ch[i][j]==1 && !vis[i][j]) {puts("-1"); return 0;}
    memset(vis,0,sizeof(vis)); dfs(sx,sy);
    while(sx!=tx || sy!=ty)
    {
        auto [x,y]=pr[sx][sy];
        if(x==sx+1) MD(1); if(x==sx-1) MD(-1);
        if(y==sy+1) MR(1); if(y==sy-1) MR(-1);
        sx=x,sy=y;
    }
    for(auto i:ans) putchar(i);
    reverse(ans.begin(),ans.end());
    for(auto i:ans) putchar(i);
    putchar('\n');
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
11
11
1 1 2 2

output:

DRDUUDRLLDUURDDRUUDLLRDUUDRD

result:

ok Valid Solution (Length = 28).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

UDDLLRRLLRRDDUUDDUUDDUUDDUURLLUDDUDDUDDDDUURLLDDUUDDUURLLUDDUDDUDDUDDDDUUDDUUDDUUDDUULLRRUDDUDDLLRRDDUUDDUULLRRUDDUDDUDDUDDRLLRLLDDUUUUDDLLRLLRDDUDDUDDUDDURRLLUUDDUUDDRRLLDDUDDURRLLUUDDUUDDUUDDUUDDDDUDDUDDUDDULLRUUDDUUDDLLRUUDDDDUDDUDDULLRUUDDUUDDUUDDUUDDRRLLRRLLDDU

result:

wrong answer (1,2) Not Visited