QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#256291#7748. Karshilov's Matching Problem IIucup-team206WA 0ms3724kbC++173.1kb2023-11-18 18:23:092023-11-18 18:23:09

Judging History

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

  • [2024-08-25 20:42:18]
  • hack成功,自动添加数据
  • (/hack/789)
  • [2023-11-18 18:23:09]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3724kb
  • [2023-11-18 18:23:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;

using fp=tuple<int,int,int,int>;

const int N=33;

int n,m;

int sx,sy,tx,ty;

char s[N][N];

int dx[]={-1,0,1,0},dy[]={0,-1,0,1};

char op[]="ULDR";

bool chk(int u,int v)
{
    if(u>=1&&u<=n&&v>=1&&v<=m&&s[u][v]=='1')
        return 1;
    return 0;
}

string opt;

vector<int> OPT;

int vis[N][N];

void dfs(int x,int y)
{
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int tx=x-dx[i],ty=y-dy[i];
        if(chk(tx,ty)&&!vis[tx][ty])
        {
            opt+=op[i];
            OPT.push_back(i);
            dfs(tx,ty);
            opt+=op[(i+2)%4];
            OPT.push_back((i+2)%4);
        }
    }
}

int ok[N][N][N][N],o[N][N][N][N];

fp pre[N][N][N][N];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    dfs(tx,ty);
    // reverse(opt.begin(),opt.end());
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(chk(i,j)&&!vis[i][j])
            {
                puts("-1");
                return 0;
            }
    int A=sx,B=sy,C=tx,D=ty;
    for(auto i:OPT)
        if(chk(A+dx[i],B+dy[i]))
            A+=dx[i],B+=dy[i];
    queue<fp>q;
    memset(ok,-1,sizeof(ok));
    ok[A][B][C][D]=0;
    q.push({A,B,C,D});
    while(!q.empty())
    {
        auto [a,b,c,d]=q.front();
        int D=ok[a][b][c][d];
        q.pop();
        for(int i=0;i<4;i++)
        {
            int na=a+dx[i],nb=b+dy[i];
            if(!chk(na,nb))
                na=a,nb=b;
            int pc=c-dx[i],pd=d-dy[i];
            if(chk(pc,pd)&&chk(na,nb)&&ok[na][nb][pc][pd]==-1)
            {
                ok[na][nb][pc][pd]=D+1;
                o[na][nb][pc][pd]=i;
                pre[na][nb][pc][pd]={a,b,c,d};
                q.push({na,nb,pc,pd});
            }
            pc=c,pd=d;
            if(!chk(c+dx[i],d+dy[i])&&chk(na,nb)&&ok[na][nb][pc][pd]==-1)
            {
                ok[na][nb][pc][pd]=D+1;
                o[na][nb][pc][pd]=i;
                pre[na][nb][pc][pd]={a,b,c,d};
                q.push({na,nb,pc,pd});
            }
        }
    }
    int mn=1e9;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(ok[i][j][i][j]!=-1)
                mn=min(mn,ok[i][j][i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(ok[i][j][i][j]==mn)
            {
                int a=i,b=j,c=i,d=j;
                string ans;
                while(a!=A||b!=B||c!=C||d!=D)
                {
                    ans+=op[o[a][b][c][d]];
                    auto [aa,bb,cc,dd]=pre[a][b][c][d];
                    a=aa,b=bb,c=cc,d=dd;
                }
                reverse(ans.begin(),ans.end());
                ans=opt+ans;
                auto rans=ans;
                reverse(rans.begin(),rans.end());
                ans+=rans;
                assert(ans.size()<=1e4);
                printf("%s\n",ans.c_str());
                return 0;
            }

    assert(0);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3724kb

input:

8 5
abbabaab
aababbab
1 2 4 8 16 32 64 128
1 1
2 3
3 5
4 7
1 8

output:

-1

result:

wrong answer 1st lines differ - expected: '1', found: '-1'