QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#638907#7751. Palindrome Pathzzuqy#WA 0ms5916kbC++142.7kb2024-10-13 17:17:112024-10-13 17:17:12

Judging History

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

  • [2024-10-13 17:17:12]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5916kb
  • [2024-10-13 17:17:11]
  • 提交

answer

#include<bits/stdc++.h>
#define N 39
using namespace std;
bool vst[N][N];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
char dir[4]={'U','D','L','R'};
char c[N][N];
string ans,ans2,mid; 
int n,m;
bool ok(int x,int y){
	if(x<1||x>n||y<1||y>m)return 0;
	if(c[x][y]=='0')return 0;
	return 1;
}
void dfs(int x,int y){
	vst[x][y]=1;
	for(int k=0;k<4;k++){
		int nx=x+dx[k],ny=y+dy[k];
		if(!ok(nx,ny))continue;
		if(vst[nx][ny])continue;
		ans+=dir[k];
		dfs(nx,ny);
		ans+=dir[k^1];
	}
}
void move(int &x,int &y,int dir){
	int nx=x+dx[dir],ny=y+dy[dir];
	if(ok(x,y))x=nx,y=ny;
}
void move(int &x,int &y,char dir){
	if(dir=='U')move(x,y,0);
	if(dir=='D')move(x,y,1);
	if(dir=='L')move(x,y,2);
	if(dir=='R')move(x,y,3);
}
int sx,sy,tx,ty;
struct node{
	int x1,y1,x2,y2;
	
	bool operator ==(const node&a){
		return x1==a.x1&&y1==a.y1&&x2==a.x2&&y2==a.y2;
	}
	bool operator !=(const node&a){
		return x1!=a.x1||y1!=a.y1||x2!=a.x2||y2!=a.y2;
	}
};
node f[N][N][N][N];
int g[N][N][N][N]; 
int main(){
	//freopen("1.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			cin>>c[i][j];
		}
	cin>>sx>>sy>>tx>>ty;
	dfs(tx,ty);
	reverse(ans.begin(),ans.end());
	for(auto i:ans)move(sx,sy,i);
	//cout<<sx<<" "<<sy<<" "<<tx<<" "<<ty<<endl;
	//cout<<ans<<endl;
	
	queue<node>q;
	q.push((node){sx,sy,tx,ty});
	while(!q.empty()){
		auto now=q.front();q.pop();
		int x=now.x1,y=now.y1,lx=now.x2,ly=now.y2;
		//cout<<x<<" "<<y<<" "<<lx<<" "<<ly<<endl;
		for(int k=0;k<4;k++){
			int nx=now.x1,ny=now.y1;
			move(nx,ny,k);
			if(!ok(lx+dx[k],ly+dy[k])){
				if(f[nx][ny][lx][ly]==(node){0,0,0,0}){
					f[nx][ny][lx][ly]=(node){x,y,lx,ly};
					g[nx][ny][lx][ly]=k;
					q.push((node){nx,ny,lx,ly});
				}
			}
			if(ok(lx-dx[k],ly-dy[k])){
				if(f[nx][ny][lx-dx[k]][ly-dy[k]]==(node){0,0,0,0}){
					f[nx][ny][lx-dx[k]][ly-dy[k]]=(node){x,y,lx,ly};
					g[nx][ny][lx-dx[k]][ly-dy[k]]=k;
					q.push((node){nx,ny,lx-dx[k],ly-dy[k]});
				}
			}
		}
	}
	//cout<<"OK"; 
	int x1=0,x2=0,y1=0,y2=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(ok(i,j)&&f[i][j][i][j]!=(node){0,0,0,0}){
				x1=i,y1=j,x2=i,y2=j;mid="";
			}
			for(int k=0;k<4;k++){
				if(ok(i,j)&&ok(i+dx[k],j+dy[k])&&f[i][j][i+dx[k]][j+dy[k]]!=(node){0,0,0,0}){
					x1=i,y1=j,x2=i+dx[k],y2=j+dy[j];
					mid=dir[k];
				} 
			}
		}
	if(x1==0){
		cout<<-1;
		return 0;
	}
	//cout<<"OK";
	while(!(x1==sx&&y1==sy&&x2==tx&&y2==ty)){
		ans2+=dir[g[x1][y1][x2][y2]];
		auto tmp=f[x1][y1][x2][y2];
		//cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
		x1=tmp.x1;y1=tmp.y1;x2=tmp.x2;y2=tmp.y2;
	}
	reverse(ans2.begin(),ans2.end());
	ans+=ans2;
	ans2=ans;
	reverse(ans2.begin(),ans2.end());
	ans+=mid+ans2;
	cout<<ans;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3920kb

input:

2 2
11
11
1 1 2 2

output:

DRUDLUDRLRDULDURD

result:

ok Valid Solution (Length = 17).

Test #2:

score: 0
Accepted
time: 0ms
memory: 5916kb

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3576kb

input:

1 1
1
1 1 1 1

output:

-1

result:

wrong answer Solution Exists, But -1 Found.