自动搬运

查看原文

来自洛谷，原作者为

	Feyn AFO

搬运于2025-08-24 22:35:12，当前版本为作者最后更新于2022-07-30 12:05:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

link

首先给每个点和它指向的点连边之后会形成一片内向基环树森林，毕竟题目中保证了不会指向矩形外的区域（虽然样例二似乎打破了这个限制但无伤大雅）。而题目中 Hansel 获胜的两种方法可以表示为：

• 从第一列某个点到最后一列某个点的路上恰好有一个彩色方块。
• 第一列某个点所在的基环树上压根没有最后一列的结点。

对于第二种情况大可以不管它，因为给这些节点染多少色都是合法的。那么对于第一种情况，基环树上路径是令人难受的。但众所周知，树加边等于基环树，换句话说基环树减边等于树。而根据题目中的设定，机器人到最后一行之后就不会再移动了（所以给最后一行的箭头干嘛呀对吧），那么我们可以把这条边断掉，这样我们就获得了一棵以最后一列结点为根的树。

这样处理完了之后呢，根据题意树上有那么一些特殊的结点（也就是第一列的结点），我们希望给树上的某些结点染色（树根是不能染色哒），然后使得每个特殊节点到树根的路径上刚好有一个染色结点。然后发现考虑每个特殊节点能被哪些点管辖到是复杂的，而考虑每个点能影响哪些特殊点是简单的，于是问题就变成了每个点能管辖一些点，要求选出一些点使得每个特殊点恰好被管辖一次。

考试完瞟了一眼官方题解，说可以用 bitmasks （位掩码）来加速这一过程，但明显我那么弱是不会这种高级东西的。如果做过同为 COCI 的 Burza 的话会发现二者最后的处理方法惊人的相似（说不定是同一个出题人出的呢）。如果用深搜序来给每个第一列的结点编号，那么每个节点能管辖的特殊点编号必然是连续的，然后就可以使用那道题一样的方法进行 DP 了，具体细节可以看那道题的相关博客，真的几乎一模一样。

输出答案方面直接在 DP 过程中记录一下是哪个状态转移过来的就可以了。还有一点就是有可能他的颜料比较多，为了刷满那么多个点我们可能需要去输出一些无用点（包括以它为根的子树内没有特殊点的点和所在基环树不包含最后一列点的点），具体看代码即可。

最后是由于这道题比较阴险，限制的是矩阵中的结点个数和而不是长宽，不能使用有序数对来代表一个位置，稍微麻烦点但其实还好，反正空间给得足（比起之前 COICI 动不动用 32M 的空间打压我等蒟蒻的题好多了）。

#include<bits/stdc++.h>
//#define feyn
#define p(i,j) ((i-1)*n+j)
const int N=1000010;
using namespace std;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}
inline int get(){
	char w=getchar();
	while(w<'A'||w>'Z')w=getchar();
	if(w=='U')return 0;
	if(w=='R')return 1;
	if(w=='D')return 2;
	if(w=='L')return 3;
}
inline int min(int s1,int s2){
	return s1<s2?s1:s2; 
}
inline int max(int s1,int s2){
	return s1<s2?s2:s1;
}

struct edge{
	int t,next;
}e[N];
int head[N],esum;
inline void add(int fr,int to){
	e[++esum]=(edge){to,head[fr]};head[fr]=esum;
}

int m,n,able;
bool ll[N],rr[N],vis[N];
inline void print(int wh){
	printf("%d %d\n",(wh-1)/n+1,(wh-1)%n+1);
}

struct node{
	int id,r;
};
vector<int>useless;
vector<node>pl[N];
int al[N],ar[N],cnt;//每个点管辖的特殊点的范围，cnt是深搜序 
void dfs(int wh){
	al[wh]=1e9;if(ll[wh])al[wh]=ar[wh]=++cnt;
	for(int i=head[wh],th;i;i=e[i].next){
		if(rr[th=e[i].t])continue;dfs(th);
		if(ar[th])al[wh]=min(al[wh],al[th]),ar[wh]=max(ar[wh],ar[th]);
	}
	if(ar[wh]==0)return;vis[wh]=true;
	pl[al[wh]].push_back((node){wh,ar[wh]});
}

bool f[N][60];//f[i][j]前i个点用了j次染色机会是否能全部染完 
int come[N][60];//记录每个状态是从哪里转移过来的 

signed main(){
	
	#ifdef feyn
	freopen("in.txt","r",stdin);
	#endif
	
	read(m);read(n);read(able);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(j==1)ll[p(i,j)]=true;
			if(j==n)rr[p(i,j)]=true;
			switch(get()){
				case 0:add(p(i-1,j),p(i,j));break;
				case 1:add(p(i,j+1),p(i,j));break;
				case 2:add(p(i+1,j),p(i,j));break;
				case 3:add(p(i,j-1),p(i,j));break;
			}
		}
	}
	for(int i=1;i<=m;i++)dfs(p(i,n));
	int num_=0;
	for(int i=1;i<=m*n;i++){
		if((i-1)%n+1==n)continue;
		if(vis[i]==false)num_++,useless.push_back(i);
	}
	
	f[0][0]=true;
	for(int i=0;i<cnt;i++){
		for(vector<node>::iterator it=pl[i+1].begin();it!=pl[i+1].end();it++){
			int _r=(*it).r,_wh=(*it).id;
			for(int k=0;k<able;k++){
				if(f[i][k]==false)continue;
				if(f[_r][k+1]==false){
					f[_r][k+1]=true;
					come[_r][k+1]=_wh;
				}
			}
		}
	}
	for(int i=0;i<=able;i++){
		if(f[cnt][i]==false)continue;
		if(able-i>num_)continue;
		able-=i;int x=cnt;
		for(int j=i;j;j--){
			print(come[x][j]);
			x=al[come[x][j]]-1;
		}
		for(int j=0;j<able;j++)print(useless[j]);
		return 0;
	}
	printf("-1");
	
	return 0;
}