QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#395457 | #7751. Palindrome Path | Xun_xiaoyao | WA | 1ms | 3772kb | C++14 | 2.2kb | 2024-04-21 14:55:52 | 2024-04-21 14:55:53 |
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++;
}
bool vid[40][40][40][40];
void calc(int stx,int sty,int enx,int eny)
{
if(vid[stx][sty][enx][eny]) return;
vid[stx][sty][enx][eny]=true;
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3580kb
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: 3772kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
DDDRUUUULLDDDDLUUUUDDDDRUUUURRDDDDLUUUUDDDDDDULUDDDDDUUULDDDDDURUDDDDDUUURDDDDDURRUDDDDDRUUUDDDDDURUDDDDDLUUUDDDDDULUDDDDDDUUUULDDDDRRUUUURDDDDUUUULDDDDLLUUUURDDD
result:
ok Valid Solution (Length = 162).
Test #5:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
DDDDRRUULRUULRRRDDLRDDLRUUUULLDDDDLLUUUUUUUULLDDDDLLUUUURLDDRLDDRRRLUURLUURRDDDD
result:
ok Valid Solution (Length = 80).
Test #6:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
5 3 111 100 111 001 111 4 3 3 2
output:
LUURRLLDDRRDDLLRRUULLUUUULLUURRLLDDRRDDLLRRUUL
result:
ok Valid Solution (Length = 46).
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 3592kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
UULLULDDDUUURUDDRDURDDUUDDRUDRDDURUUUDDDLULLUU
result:
wrong answer (5,3) Not Visited