列表

详情

NC230853. Cross the Maze

描述

"Ad astra abyssoque."

The adventurers from Teyvat are trapped in a rectangular maze of square cells, which is surrounded by walls from the outside. The floorboards of the maze are so fragile that no two adventurers are allowed moving to or staying in the same cell of the maze anytime.

When they are trying to cross the maze, they find n escape ropes in the maze and realize that the number of the escape ropes in the maze is exactly the same as the number of the adventurers trapped in the maze. However, the escape ropes are of low quality that a rope breaks immediately when an adventurer escape from the maze with it.

In every second, each of the adventurers can independently and simultaneously move from the cell (x,y) to left cell (x,y-1), the right cell , the upper cell (x-1,y), the lower cell in the maze, or just stay in place. When reaching a cell contains an intact escape rope after moving, an adventurer can decide to get out of the maze with the help of the escape rope immediately and then the rope breaks, or stay in the maze and leave the escape rope for others. Note that an adventurer can also leave the maze before moving if the adventurer has already located at a cell contains an escape rope.

Lumine the traveller wants to guide all the trapped adventurers cross the maze as soon as possible that she can continue searching for her family.

输入描述

The first line contains three positive integers n , a and b , denoting the number of the adventurers trapped in the maze as well as the number of the escape ropes in the maze and the number of rows and columns in the maze.

Then follow n lines, each of which contains two integers s_x  and s_y , denoting an adventurer located at the cell (s_x,s_y) in the maze initially. All the adventurers are located at different cells initially.

Then again follow n lines, each of which contains two integers e_x  and e_y , denoting an escape rope located at the cell (e_x,e_y) in the maze. All the escape ropes are located at different cells.

It is guaranteed that at least one adventurer located at the cell without escape ropes initially.

输出描述

The first line contains an integer t, denoting the minimum time in seconds needed for all the trapped adventurers crossing the maze.

Then output n lines, each of which contains four integers s_x, s_y, e_x and e_y, followed by a string of length t. It means that an adventurer located at the cell (s_x, s_y) initially will get out of the maze with the escape rope located at the cell (e_x, e_y) by taking actions according to the string. The i-th character in the string points out the action taken in the i-th second, where 'L' means going to the left cell, 'R' means going to the right cell, 'U' means going to the upper cell, 'D' means going to the lower cell, 'S' means staying in place, and 'P' means the adventurer has left the maze and never goes back.

If there are multiple solutions, you may output any.

示例1

输入: 

3 4 4
1 1
1 4
4 4
1 3
2 3
2 4

输出: 

2
1 1 1 3 RR
1 4 2 3 DL
4 4 2 4 UU

示例2

输入: 

3 2 2
1 1
1 2
2 2
1 1
2 1
2 2

输出: 

1
1 1 1 1 P
1 2 2 2 D
2 2 2 1 L

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 7ms, 内存消耗: 1444K, 提交时间: 2021-11-21 15:30:13 

#include<bits/stdc++.h>
using namespace std;
const int N = 44444;
const int M = 444444;
const int A = 222;
const int inf = 1e9;
struct edge{
	int to;
	int ca;
	int pr;
}e[M];
int tot=1,la[N],mx;
int n,d[N],f[N],a,b,sx[N],sy[N],tx[N],ty[N];
void adde(int x,int y,int z){
	e[++tot].to=y;
	e[tot].ca=z;
	e[tot].pr=la[x];
	la[x]=tot;
}
void addf(int x,int y,int z=1){
	adde(x,y,z);
	adde(y,x,0);
}
int G(int i,int j,int t,int z){
	return (i*b+j+t*a*b)*2+z+A;
}
int s,t;
queue<int> q;
int bfs(){
	int i,x,y;
	for(i=1;i<=mx;i++)
		d[i]=inf;
	d[s]=1;
	q.push(s);
	while(!q.empty()){
		x=q.front();
		q.pop();
		for(i=la[x];i;i=e[i].pr){
			if(!e[i].ca)
				continue;
			y=e[i].to;
			if(d[y]>d[x]+1){
				d[y]=d[x]+1;
				q.push(y);
			}
		}
	}
	if(d[t]>=inf)
		return 0;
	return 1;
}
int dfs(int x,int fl){
	if(x==t)
		return fl;
	int i,y,r=0,o;
	for(i=la[x];i;i=e[i].pr){
		if(!e[i].ca)
			continue;
		y=e[i].to;
		if(d[y]!=d[x]+1)
			continue;
		o=dfs(y,min(fl,e[i].ca));
		fl-=o;
		r+=o;
		e[i].ca-=o;
		e[i^1].ca+=o;
	}
	if(!r)
		d[x]=0;
	return r;
}
int flow;
void maxflow(){
	while(bfs()){
		//cout<<32214;
		flow+=dfs(s,inf);
		//cout<<flow<<endl;
	}
}
char c[1111];
int l,fx,fy;
void go(int u,int x,int y){
	int i,z,xx,yy;
	for(i=la[u];i;i=e[i].pr){
		if((i%2==0)&&!e[i].ca){
			e[i].ca++;
			z=e[i].to;
			if(z<A){
				//cout<<z-t<<endl;
				fx=tx[z-t];
				fy=ty[z-t];
				return;
			}
			//cout<<x<<' '<<y<<' '<<xx<<' '<<yy<<endl;
			xx=(z-A)/2%(a*b)/b;
			yy=(z-A)/2%b;
			if(xx<x)
				c[l++]='U';
			if(xx>x)
				c[l++]='D';
			if(yy<y)
				c[l++]='L';
			if(yy>y)
				c[l++]='R';
            if(x==xx&&y==yy)
				c[l++]='S';
			go(G(xx,yy,l,1),xx,yy);
			return;
		}
	}
}
int main(){
	int i,j,k;
	scanf("%d%d%d",&n,&a,&b);
	for(i=1;i<=n;i++)
		scanf("%d%d",sx+i,sy+i),sx[i]--,sy[i]--;
	for(i=1;i<=n;i++)
		scanf("%d%d",tx+i,ty+i),tx[i]--,ty[i]--;
	s=1,t=2;
	for(i=1;i<=n;i++){
		addf(s,G(sx[i],sy[i],0,1));
		addf(G(tx[i],ty[i],0,1),t+i);
		addf(t+i,t);
	}
	mx=a*b*2+A;
	for(k=0;1;k++){//cout<<k<<' '<<mx<<' '<<tot<<endl;
		maxflow();//cout<<k<<endl;
		if(flow==n){
			printf("%d\n",k);
			for(i=1;i<=n;i++){
				l=0;
				go(G(sx[i],sy[i],0,1),sx[i],sy[i]);
				while(l<k){
					c[l++]='P';
				}
				c[l]=0;
				printf("%d %d %d %d %s\n",sx[i]+1,sy[i]+1,fx+1,fy+1,c);
			}
			return 0;
		}
		for(i=0;i<a;i++)
			for(j=0;j<b;j++){
				addf(G(i,j,k,1),G(i,j,k+1,0));
				if(i)
					addf(G(i,j,k,1),G(i-1,j,k+1,0));
				if(i+1<a)
					addf(G(i,j,k,1),G(i+1,j,k+1,0));
				if(j)
					addf(G(i,j,k,1),G(i,j-1,k+1,0));
				if(j+1<b)
					addf(G(i,j,k,1),G(i,j+1,k+1,0));
				addf(G(i,j,k+1,0),G(i,j,k+1,1));
			}
		for(i=1;i<=n;i++)
			addf(G(tx[i],ty[i],k+1,1),t+i);
		mx+=a*b*2;
	}
}

上一题

© 2024 nowcoder.com