自动搬运

查看原文

来自洛谷，原作者为

	liuzimingc You will never live if you are looking for the meaning of life.

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

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

以下是正文

纪念一下在模拟赛中赛时唯一过的一道题，喜提倒数不知道多少名 :)

不需要差分约束的做法，没有 $\log$。

考虑把图上的每个位置看成一个点，我们考虑直接算出每个 # 点会下落多少高度。

首先如果是在一个连通块里的，可以直接连边权为 $0$ 的边，因为肯定是一起停止的，下落高度相同。可以 DFS 处理，时间复杂度 $\mathcal O(nm)$。

然后应该怎么做呢？模拟下落操作，对于形如下面的东西：

.
.

和

#
.

都需要下落，所以我们考虑从上往下连一条边权为 $1$ 的边。而对于：

.
#

就直接停住了。所以从上往下连一条边权为 $0$ 的边。

因为停止是算最先停住的位置，连完之后跑一个最短路就好了。但是边权只有 $0$ 和 $1$，直接 01BFS，可以做到整体 $\mathcal O(nm)$。

namespace liuzimingc {
#define endl '\n'
#define pii pair<int, int>
const int N = 1e6 + 5, INF = 1e9;
const int dx[] = { -1, 1, 0, 0 }, dy[] = { 0, 0, -1, 1 };

int n, m, tot, dis[N];
bool vis[N], id[N];
vector<int> v;
vector<char> s[N], ans[N];
deque<pii> q;
vector<pii> e[N];
char str[N];

int get(int x, int y) { return (x - 1) * m + y; }

void dfs(int x, int y, int lst) {
	id[get(x, y)] = true;
	if (lst) e[lst].push_back({ get(x, y), 0 }), e[get(x, y)].push_back({ lst, 0 });
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 1 || nx > n || ny < 1 || ny > m || id[get(nx, ny)] || s[nx][ny] == '.') continue;
		dfs(nx, ny, get(x, y));
	}
}

void bfs() {
	for (int i = 1; i <= n * m; i++) dis[i] = INF;
	for (int i = 1; i <= m; i++) q.push_back({ get(n, i), 0 });
	while (q.size()) {
		int u = q.front().first, d = q.front().second; q.pop_front();
		if (vis[u]) continue;
		vis[u] = true;
		dis[u] = d;
		for (const auto &i : e[u]) {
			int v = i.first, w = i.second;
			if (!w) q.push_front({ v, d });
			else q.push_back({ v, d + 1 });
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		s[i].resize(m + 1);
		ans[i].resize(m + 1);
		cin >> (str + 1);
		for (int j = 1; j <= m; j++) s[i][j] = str[j];
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (!id[get(i, j)] && s[i][j] == '#') dfs(i, j, 0);
	for (int i = 1; i < n; i++)
		for (int j = 1; j <= m; j++)
			if (s[i + 1][j] == '.') e[get(i + 1, j)].push_back({ get(i, j), 1 });
			else if (s[i][j] == '.') e[get(i + 1, j)].push_back({ get(i, j), 0 });
	bfs();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (s[i][j] == '#') ans[i + dis[get(i, j)]][j] = '#';
	for (int i = 1; i <= n; i++, cout << endl)
		for (int j = 1; j <= m; j++)
			cout << (ans[i][j] ? ans[i][j] : '.');
	return 0;
}
} // namespace liuzimingc