自动搬运

查看原文

来自洛谷，原作者为

	THM200000000 正在输入中......

搬运于2025-08-24 22:23:41，当前版本为作者最后更新于2024-10-02 16:26:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P6757 Tracks in the Snow 题解

题意

有两种小动物从一个矩阵的左上角开始到处乱逛，到右下角结束，每一时刻仅有一只小动物在矩阵上，狐狸走过的地方被标记为 F，兔子走过的地方被标记为 R，无小动物经过的点为 .，标记可被覆盖，先给出最后的矩阵，问至少有几只小动物经过。

思路

由于脚印可以覆盖，那么下一只小动物经过的地方上一只使可以随便踩的，故考虑倒推。为了使经过的小动物最少，在倒推过程中每只小动物必须将可以踩的地方都踩完，所以可以理解为是一个不断扩散联通块的过程。

同样可以证明，两种小动物交替经过（即不会出现连续两次经过同样的动物）时，实现给出矩阵所需的小动物最少。

实现

在经过上述分析之后，想要实现并不难，只需不断洪水填充不断取反和扩张，直到填完所有 F 和 R 即可，假设需要填充 $x$ 次才能结束，那么算法的复杂度为 $O(nmx)$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define chg(x) (x == 'R'? 'F' : 'R') //宏定义，便于在填充时进行取反 
char a[4010][4010];
int n, m;
int filled; //记录每次填充的面积
int now; //记录当前填充的面积
int ans; //结果，即需要填充的次数
void dfs(int x, int y, char tp) { //洪水填充
	if(a[x][y] != tp) return ;
	if(x == 0 || x == n + 1 || y == 0 || y == m + 1) return ; //判边界
	a[x][y] = chg(tp); //取反
	++filled; //填充时记录一次
	dfs(x + 1, y, tp);
	dfs(x - 1, y, tp);
	dfs(x, y + 1, tp);
	dfs(x, y - 1, tp);
}
signed main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i] + 1;
	do {
		now = filled;
		filled = 0;
		dfs(1, 1, a[1][1]);
		++ans;
	} while(filled > now); //验证是否与上一次重合，如果是，则跳出循环
	cout << ans - 1; //由于需要多花一次填充来判断是否结束，所以输出时应减一 
	return 0;
}

然而结果不尽人意，只有可怜的 55 分。

看到评测结果的 TLE 和 MLE 不难想到其实是因为大量得重复搜索导致的，由于本代码是不断洪水填充来达到扩张的，根本目的是扩张，那么原来搜过的地方就不用搜了。

How? 可在每次搜索时通过栈（或者队列，原理相似）来存储下次搜索的起点，再次搜索时就由这些位置开始（当然在栈中同属一个联通快的点只搜一次就行了，其他的点可以舍去）这样就可以大量地跳过搜过的区域了，复杂度 $O(nm)$。

由于计入下次搜的起点的时候约等于实在找联通快的边界，那么数组大小开到矩阵面积的一半（即 $8\times10^6$）即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define chg(x) (x == 'R'? 'F' : 'R') //宏定义，便于将足迹取反 
struct point {
	int x, y;
};
char a[4010][4010];
bool vis[4010][4010];
int n, m;
point nxt[80000010]; //以栈的形式记录当前下一次开始填充的位置
point now[80000010];           //记录当前开始填充的位置
int t; //充当nxt[]的栈顶指针
int l; //表示now[]的长度
char tp;
int ans; //结果，即需要填充的次数
void dfs(int x, int y) { //洪水填充
	if(a[x][y] == '.' || vis[x][y]) return ;
	if(a[x][y] == chg(tp)) {
		nxt[++t] = {x, y}; //存入下次开始填充的位置
		return ;
	}
	if(x == 0 || x == n + 1 || y == 0 || y == m + 1) return ;
	vis[x][y] = true; //标记
	dfs(x + 1, y);
	dfs(x - 1, y);
	dfs(x, y + 1);
	dfs(x, y - 1);
}
signed main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i] + 1; //读入（废话
	t = 1;
	nxt[t] = {1, 1};
	tp = a[1][1]; //记录开始填充时对应的符号
	do {
		if(t) {
			l = t;
			for(int i = 1; i <= l; i++)
				now[i] = nxt[i]; //刷新填充起点
			t = 0;
			for(int i = 1; i <= l; i++) {
				if(!vis[now[i].x][now[i].y])
					dfs(now[i].x, now[i].y);
			}
			++ans;
		} else break;
		tp = chg(tp); //取反
	} while(t); //验证是否能继续搜
	cout << ans;
	return 0;
}

可见评测结果绿了不少，但是区区 92 分我们是绝对不能满意的。由于数组开的全是静态，所以 MLE 的罪魁祸首只能是洪水填充的过程，怎么处理呢？由于当我们存入下次搜索时的数据结构的栈，那么这事我不禁想起了当年学深搜用的幼儿园写法：用栈来搜（当然如果存的时候用的是队列那么广搜也是可以的）。这样可以大大减少递归时消耗的内存，那么这里不多解释，代码里见！

#include<bits/stdc++.h>
#define I return
#define AK 0
#define IOI ;
using namespace std;
#define chg(x) (x == 'R'? 'F' : 'R') //宏定义，便于将足迹取反 
struct point { //定义结构体，便于入栈 
	int x, y;
};
char a[4010][4010]; //读入的矩阵
bool vis[4010][4010]; //用以标记搜过的位置（这应该不用过多解释吧）
int n, m; //矩阵长宽
point nxt[80000010]; //以栈的形式记录当前下一次开始填充的位置
point now[160000010]; //栈，用于DFS
int t; //充当nxt[]的栈顶指针
int l; //表示now[]的长度
int ans; //结果，即需要填充的次数
point tmp; //表示DFS过程中当前搜到的位置
void dfs(char tp) { //洪水填充
	while(l) {
		tmp = now[l--];
		if(a[tmp.x][tmp.y] == chg(tp)) {
			nxt[++t] = tmp; //存入下次开始填充的位置
			continue;
		}
		vis[tmp.x][tmp.y] = true; //标记
		if(a[tmp.x + 1][tmp.y] != '.' && !vis[tmp.x + 1][tmp.y] && tmp.x != n) //入栈
			now[++l] = {tmp.x + 1, tmp.y};
		if(a[tmp.x - 1][tmp.y] != '.' && !vis[tmp.x - 1][tmp.y] && tmp.x != 1)
			now[++l] = {tmp.x - 1, tmp.y};
		if(a[tmp.x][tmp.y + 1] != '.' && !vis[tmp.x][tmp.y + 1] && tmp.y != m)
			now[++l] = {tmp.x, tmp.y + 1};
		if(a[tmp.x][tmp.y - 1] != '.' && !vis[tmp.x][tmp.y - 1] && tmp.y != 1)
			now[++l] = {tmp.x, tmp.y - 1};
	}
}
signed main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i] + 1; //读入（废话
	t = 1;
	nxt[t] = {1, 1}; //将搜索的起点压栈
	int tp = a[nxt[t].x][nxt[t].y]; //记录开始填充时对应的符号
	do {
		if(t) {
			l = t;
			for(; t; --t)
				now[t] = nxt[t]; //刷新填充起点
			for(int i = 1; i <= l; i++) {
				if(!vis[now[i].x][now[i].y]) //排除已经搜过但仍在栈中的情况
					dfs(tp);
			}
			++ans;
		} else break;
		tp = chg(tp); //取反
	} while(t); //验证是否能继续搜
	cout << ans;
	I AK IOI; //完美收场
}

结果：$\huge\textrm {完美无瑕}$

50 个点AC真的爽！

另外蒟蒻调代码调了三个多小时，题解写了也近一个小时，甚至最后的代码都是在回家路上的地铁上写的......可以......留个小小的赞吗= )。