QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#394449#7751. Palindrome PathtanxiRE 0ms0kbC++143.5kb2024-04-20 14:51:302024-04-20 14:51:31

Judging History

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

  • [2024-04-20 14:51:31]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-04-20 14:51:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char ch[4]={'R','L','D','U'};
int f[39][39][4];
int a[39][39],vis[39][39];
pair<int,int>stk[N];
int top,n,m;
void dfs(int x,int y)
{
    vis[x][y]=1;
    stk[++top]={x,y};
    for(int t=0;t<4;t++)
    {
        int nx=x+dx[t];
        int ny=y+dy[t];
        if(!a[nx][ny])
        continue;
        if(vis[nx][ny])
        continue;
        dfs(nx,ny);
        stk[++top]={x,y};
    }
}
int stx,sty,edx,edy;
string s;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    freopen("er.err","w",stderr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char c;
            cin>>c;
            a[i][j]=c-'0';
        }
    }
    cin>>stx>>sty>>edx>>edy;
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!a[i][j])
            {
                f[i][j][3]=f[i][j][1]=-1;
            }
            else
            {
                f[i][j][3]=f[i-1][j][3]+1;
                f[i][j][1]=f[i][j-1][1]+1;
            }
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=n;j>=1;j--)
        {
            if(!a[i][j])
            {
                f[i][j][2]=f[i][j][0]=-1;
            }
            else
            {
                f[i][j][2]=f[i+1][j][2]+1;
                f[i][j][0]=f[i][j+1][0]+1;
            }
        }
    }
    dfs(stx,sty);
    if(!vis[edx][edy])
    {
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=top;i++)
    {
        stk[++top]=stk[i];
        if(stk[i].first==edx&&stk[i].second==edy)
        break;
    }
    for(int i=1;i<top;i++)
    {
        int x=stk[i].first,y=stk[i].second;
        for(int t=0;t<4;t++)
        {
            if(stk[i+1].first==x+dx[t]&&stk[i+1].second==y+dy[t])
            {
                // cerr<<x<<','<<y<<"to"<<stk[i+1].first<<','<<stk[i+1].second<<'\n';
                int k=f[x][y][t^1];
                int p=f[edx][edy][t];
                if(k==p)
                {
                    for(int j=1;j<=k;j++)
                    {
                        s+=ch[t^1];
                        // cerr<<ch[t^1];
                    }
                    for(int j=1;j<=k+1;j++)
                    {
                        s+=ch[t];
                        // cerr<<ch[t];
                    }
                }
                else
                if(k>p)
                {
                    for(int j=1;j<=p;j++)
                    {
                        s+=ch[t^1];
                        // cerr<<ch[t^1];
                    }
                    for(int j=1;j<=p+1;j++)
                    {
                        s+=ch[t];
                        // cerr<<ch[t];
                    }
                }
                else
                {
                    for(int j=1;j<=k+1;j++)
                    {
                        s+=ch[t^1];
                        // cerr<<ch[t^1];
                    }
                    for(int j=1;j<=k+1;j++)
                    {
                        s+=ch[t];
                        // cerr<<ch[t];
                    }
                }
                // cerr<<'\n';
                break;
            }
        }
    }
    cout<<s;
    reverse(s.begin(),s.end());
    cout<<s;
    return 0;
}

詳細信息

Test #1:

score: 0
Dangerous Syscalls

input:

2 2
11
11
1 1 2 2

output:


result: