QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#395456 | #7751. Palindrome Path | Xun_xiaoyao | RE | 1ms | 3732kb | C++14 | 2.1kb | 2024-04-21 14:54:04 | 2024-04-21 14:54:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int Qread()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x;
}
int get_ch()
{
char ch=getchar();
while(ch!='0'&&ch!='1') ch=getchar();
return ch=='1';
}
bool fin,vis[40][40],mp[40][40];
int n,m,stx,sty,enx,eny;
char stk[810010];int top;
void dfs(int x,int y)
{
vis[x][y]=true;
if(x>1&&mp[x-1][y]&&!vis[x-1][y])
{
stk[++top]='U';
dfs(x-1,y);
stk[++top]='D';
}
if(x<n&&mp[x+1][y]&&!vis[x+1][y])
{
stk[++top]='D';
dfs(x+1,y);
stk[++top]='U';
}
if(y>1&&mp[x][y-1]&&!vis[x][y-1])
{
stk[++top]='L';
dfs(x,y-1);
stk[++top]='R';
}
if(y<m&&mp[x][y+1]&&!vis[x][y+1])
{
stk[++top]='R';
dfs(x,y+1);
stk[++top]='L';
}
}
void tkop(int &x,int &y,char op)
{
if(op=='U'&&x>1&&mp[x-1][y]) x--;
if(op=='D'&&x<n&&mp[x+1][y]) x++;
if(op=='L'&&y>1&&mp[x][y-1]) y--;
if(op=='R'&&y<m&&mp[x][y+1]) y++;
}
void calc(int stx,int sty,int enx,int eny)
{
if(stx==sty&&enx==eny)
{
for(int i=1;i<=top;i++) putchar(stk[i]);
reverse(stk+1,stk+top+1);
for(int i=1;i<=top;i++) putchar(stk[i]);
exit(0);
}
int x_,y_;
top++;
tkop(x_=stx,y_=sty,stk[top]='U');
if(enx==1||!mp[enx-1][eny]) calc(x_,y_,enx,eny);
if(enx<n&&mp[enx+1][eny]) calc(x_,y_,enx+1,eny);
tkop(x_=stx,y_=sty,stk[top]='D');
if(enx==n||!mp[enx+1][eny]) calc(x_,y_,enx,eny);
if(enx>1&&mp[enx-1][eny]) calc(x_,y_,enx-1,eny);
tkop(x_=stx,y_=sty,stk[top]='L');
if(enx==1||!mp[enx][eny-1]) calc(x_,y_,enx,eny);
if(eny<m&&mp[enx][eny+1]) calc(x_,y_,enx,eny+1);
tkop(x_=stx,y_=sty,stk[top]='R');
if(enx==m||!mp[enx][eny+1]) calc(x_,y_,enx,eny);
if(enx>1&&mp[enx][eny-1]) calc(x_,y_,enx,eny-1);
top--;
}
int main()
{
n=Qread(),m=Qread();
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
mp[i][j]=get_ch();
stx=Qread(),sty=Qread(),enx=Qread(),eny=Qread();
dfs(enx,eny);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
if(mp[i][j]&&!vis[i][j])
return printf("-1\n"),0;
reverse(stk+1,stk+top+1);
for(int i=1;i<=top;i++)
tkop(stx,sty,stk[i]);
calc(stx,sty,enx,eny);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3704kb
input:
2 2 11 11 1 1 2 2
output:
DRUDLUULDURD
result:
ok Valid Solution (Length = 12).
Test #2:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: -100
Runtime Error
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2