QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#256291 | #7748. Karshilov's Matching Problem II | ucup-team206 | WA | 0ms | 3724kb | C++17 | 3.1kb | 2023-11-18 18:23:09 | 2023-11-18 18:23:09 |
Judging History
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'