QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352666#7751. Palindrome PathGraphcityWA 0ms3676kbC++201.9kb2024-03-13 14:58:322024-03-13 14:58:32

Judging History

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

  • [2024-03-13 14:58:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3676kb
  • [2024-03-13 14:58:32]
  • 提交

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');}
}

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();
    if(!vis[sx][sy]) {puts("-1"); return 0;}
    while(sx!=tx || sy!=ty)
    {
        auto [x,y]=pr[sx][sy];
        if(x==sx+1) MR(1); if(x==sx-1) MR(-1);
        if(y==sy+1) MD(1); if(y==sy-1) MD(-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: 0
Wrong Answer
time: 0ms
memory: 3676kb

input:

2 2
11
11
1 1 2 2

output:

DRRD

result:

wrong answer (1,2) Not Visited