QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#352675 | #7751. Palindrome Path | Graphcity | WA | 0ms | 3956kb | C++20 | 2.3kb | 2024-03-13 15:03:25 | 2024-03-13 15:03:25 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=30;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int n,m,ch[35][35],sx,sy,tx,ty;
int vis[35][35]; pair<int,int> pr[35][35];
vector<char> ans;
inline int chk(int x,int y)
{return (x>=1 && x<=n && y>=1 && y<=m && ch[x][y]==1);}
inline void bfs()
{
queue<pair<int,int>> q;
vis[tx][ty]=1,q.emplace(tx,ty);
while(!q.empty())
{
auto [x,y]=q.front(); q.pop();
For(_,0,3)
{
int x1=x+dx[_],y1=y+dy[_];
if(!chk(x1,y1) || vis[x1][y1]) continue;
vis[x1][y1]=1,pr[x1][y1]=make_pair(x,y),q.emplace(x1,y1);
}
}
}
inline void MR(int op)
{
int x1=sx,y1=sy,x2=tx,y2=ty,cnt=0;
while(chk(x1,y1-op) && chk(x2,y2+op)) ans.push_back(op==1?'L':'R'),y1-=op,y2+=op,cnt++;
if(!chk(x2,y2+op)) {For(i,1,cnt+1) ans.push_back(op==1?'R':'L');}
else {ans.push_back(op==1?'L':'R'); For(i,1,cnt+1) ans.push_back(op==1?'R':'L');}
}
inline void MD(int op)
{
int x1=sx,y1=sy,x2=tx,y2=ty,cnt=0;
while(chk(x1-op,y1) && chk(x2+op,y2)) ans.push_back(op==1?'U':'D'),x1-=op,x2+=op,cnt++;
if(!chk(x2+op,y2)) {For(i,1,cnt+1) ans.push_back(op==1?'D':'U');}
else {ans.push_back(op==1?'U':'D'); For(i,1,cnt+1) ans.push_back(op==1?'D':'U');}
}
inline void dfs(int x,int y)
{
vis[x][y]=1;
For(_,0,3)
{
int x1=x+dx[_],y1=y+dy[_];
if(!chk(x1,y1) || vis[x1][y1]) continue;
if(x1==x+1) MD(1); if(x1==x-1) MD(-1);
if(y1==y+1) MR(1); if(y1==y-1) MR(-1);
dfs(x1,y1);
if(x1==x+1) MD(-1); if(x1==x-1) MD(1);
if(y1==y+1) MR(-1); if(y1==y-1) MR(1);
}
}
int main()
{
// freopen("1.in","r",stdin);
cin>>n>>m;
For(i,1,n) For(j,1,m) scanf("%1d",&ch[i][j]);
cin>>sx>>sy>>tx>>ty; bfs();
For(i,1,n) For(j,1,m) if(ch[i][j]==1 && !vis[i][j]) {puts("-1"); return 0;}
memset(vis,0,sizeof(vis)); dfs(sx,sy);
while(sx!=tx || sy!=ty)
{
auto [x,y]=pr[sx][sy];
if(x==sx+1) MD(1); if(x==sx-1) MD(-1);
if(y==sy+1) MR(1); if(y==sy-1) MR(-1);
sx=x,sy=y;
}
for(auto i:ans) putchar(i);
reverse(ans.begin(),ans.end());
for(auto i:ans) putchar(i);
putchar('\n');
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3648kb
input:
2 2 11 11 1 1 2 2
output:
DRDUUDRLLDUURDDRUUDLLRDUUDRD
result:
ok Valid Solution (Length = 28).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3668kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
UDDLLRRLLRRDDUUDDUUDDUUDDUURLLUDDUDDUDDDDUURLLDDUUDDUURLLUDDUDDUDDUDDDDUUDDUUDDUUDDUULLRRUDDUDDLLRRDDUUDDUULLRRUDDUDDUDDUDDRLLRLLDDUUUUDDLLRLLRDDUDDUDDUDDURRLLUUDDUUDDRRLLDDUDDURRLLUUDDUUDDUUDDUUDDDDUDDUDDUDDULLRUUDDUUDDLLRUUDDDDUDDUDDULLRUUDDUUDDUUDDUUDDRRLLRRLLDDU
result:
wrong answer (1,2) Not Visited