自动搬运

查看原文

来自洛谷，原作者为

	xiaolilsq 灰名不比红名好看（

搬运于2025-08-24 22:21:50，当前版本为作者最后更新于2020-05-13 13:32:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

思维题。

首先，由于题目中所给的权值均为正整数（“每个单元格都有一个与之相关的正整数值”），所以我们肯定会贪心地尽量选完，如果$r$和$c$有一个是奇数，我们肯定是可以全部走完的，见下图：

但是如果$r,c$都是偶数呢？貌似无法走完所有位置了，必须要舍弃一些格子。

如何舍弃？先将地图黑白染色：

起点和终点都是黑色的，不难发现，黑色格子下一步只能到白色格子，白色格子下一步只能到黑色格子，而由于起点和终点都是黑色格子，那么经过的步数必然是奇数，经过白色格子的个数必然要比经过黑色格子的个数少1，黑色格子一共有$r\cdot c/2$个，白色一样的，所以地图中至少有一个白色格子不会经过，贪心地想，我们肯定会选择权值最小的那个白色格子去掉。

但是是不是去掉任何一个白色格子都能走完所有地图呢？可以先在草稿纸上随便画画：

貌似是的！无论去掉哪个白色格子，我们都可以一次性走完其他所有格子。

如果白色格子是在偶数行，有如下走法（红色的是被去掉的格子，可能比较丑，就将就看看吧）：

如果是在奇数行，可以通过旋转使得白色格子到偶数行去。

由此我们便得到了这道题目的一种解法。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>inline void read(T&x){
	int f;char c;
	for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>inline void write(T x){
	static char q[64];int cnt=0;
	if(!x)pc('0');if(x<0)pc('-'),x=-x;
	while(x)q[cnt++]=x%10+'0',x/=10;
	while(cnt--)pc(q[cnt]);
}
char Ans[4]={'D','R','U','L'};
int main(){
	int r,c,mn=0x3f3f3f3f,mnx=0,mny=0;
	read(r),read(c);
	for(int i=0;i<r;++i){
		for(int j=0;j<c;++j){
			int x;read(x);
			if((i+j)&1){
				if(x<mn){
					mn=x,mnx=i,mny=j;
				}
			}
		}
	}
	int p=false;
	if((r&1)||(c&1)){
		if(!(r&1))p=true,swap(r,c);
		for(int i=1;i<r;i+=2){
			for(int j=1;j<c;++j)
				putchar(Ans[1^p]);
			putchar(Ans[0^p]);
			for(int j=1;j<c;++j)
				putchar(Ans[3^p]);
			putchar(Ans[0^p]);
		}
		for(int i=1;i<c;++i)
			putchar(Ans[1^p]);
	}
	else{
		if(mny&1)p=true,swap(mnx,mny),swap(r,c);
		for(int i=1;i<mny;i+=2){
			for(int j=1;j<r;++j)
				putchar(Ans[0^p]);
			putchar(Ans[1^p]);
			for(int j=1;j<r;++j)
				putchar(Ans[2^p]);
			putchar(Ans[1^p]);
		}
		putchar(Ans[1^p]);
		for(int i=2;i<mnx;i+=2){
			putchar(Ans[0^p]);
			putchar(Ans[3^p]);
			putchar(Ans[0^p]);
			putchar(Ans[1^p]);
		}
		putchar(Ans[0^p]);
		for(int i=mnx+2;i<r;i+=2){
			putchar(Ans[0^p]);
			putchar(Ans[3^p]);
			putchar(Ans[0^p]);
			putchar(Ans[1^p]);
		}
		for(int i=mny+2;i<c;i+=2){
			putchar(Ans[1^p]);
			for(int j=1;j<r;++j)
				putchar(Ans[2^p]);
			putchar(Ans[1^p]);
			for(int j=1;j<r;++j)
				putchar(Ans[0^p]);
		}
	}
	return 0;
}