自动搬运

查看原文

来自洛谷，原作者为

	yqr123YQR 汝若将降世， 切忌罪行恶果，唯使光明降临

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

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

以下是正文

稍显幼稚的小游戏轻松快乐简单小模拟，考察基本广搜 / 深搜判连通块。

题意

每次打破一个方格上的 矿物，然后使单独的“腾空”连通块一直下落，直至与其他连通块相接 / 落至地面。请模拟此操作，矩阵大小 $r\times c$，$1\leqslant r,c\leqslant100$。

分析

这有什么好分析的？

唯一一点点问题在于，题中遵循真实物理定律的“下落”。

1. 确定下落的是哪个块

由于 数据范围与约定 中 “保证在任何时间点都不会有两个或两个以上的碎块群同时落下”，我们可以在被破坏的方格四周轻松找出两个连通块，每个都执行一次下落操作即可。

2. 下落的实现

简单粗暴地，对于每个连通块中的点，往下依次找，直到碰到地面 / 其他连通块，最后整体下移。

代码

#include<stdio.h>
#include<queue>
using namespace std;
const int maxn = 100;
int r, c, n, cnt, vis[maxn + 5][maxn + 5], dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
char mp[maxn + 5][maxn + 5];
bool isstone(int x, int y) {return x <= r && x && y <= c && y && mp[x][y] == 'x';}
struct node {int x, y;};
void bfs(int sx, int sy, int tag)//对点 (sx,sy) 所在连通块打上 tag 的标记
{
	queue<node> q;
	q.push({sx, sy});
	vis[sx][sy] = tag;
	while(!q.empty())
	{
		node t = q.front();
		q.pop();
		for(int i = 0; i < 4; i++)
		{
			int nx = t.x + dx[i], ny = t.y + dy[i];
			if(isstone(nx, ny) && !vis[nx][ny]) vis[nx][ny] = tag, q.push({nx, ny});
		}
	}
}
void calc()//重新计算每个点所属连通块
{
	for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) vis[i][j] = 0;
	cnt = 0;
	for(int i = 1; i <= r; i++)
		for(int j = 1; j <= c; j++)
			if(isstone(i, j) && !vis[i][j]) bfs(i, j, ++cnt);
}
void down(int tag)//下落标记为 tag 的连通块
{
	int ans = r + 1;
	for(int i = 1; i <= r; i++)
	{
		for(int j = 1; j <= c; j++)
		{
			if(vis[i][j] == tag)
			{
				int dis = 0;
				while(dis <= r - i && (mp[i + dis][j] == '.' || vis[i + dis][j] == tag)) dis++;
				ans = ans < --dis? ans: dis;
			}
		}
	}
	for(int i = r; i > ans; i--)
	{
		for(int j = 1; j <= c; j++)
		{
			if(vis[i - ans][j] == tag) mp[i - ans][j] = '.', mp[i][j] = 'x';
		}
	}
}
void goal(int height, int side)//射出木棍
{
	int fst = -1;
	for(int i = side == 1? 1: c; i && i <= c; i += side)
	{
		if(mp[height][i] == 'x')
		{
			fst = i;
			break;
		}
	}
	if(!~fst) return;
	mp[height][fst] = '.';
	calc();
//	for(int i = 1; i <= r; i++)
//	{
//		for(int j = 1; j <= c; j++) printf("%d ", vis[i][j]);
//		puts("");
//	}
	int id = -1;
	for(int i = 0; i < 4; i++)
	{
		int nx = height + dx[i], ny = fst + dy[i];
		if(isstone(nx, ny))
		{
			if(~id && id != vis[nx][ny])
			{
//				puts("ff");
				down(id), down(vis[nx][ny]);
				break;
			}
			id = vis[nx][ny];
		}
	}
}
int main()
{
	scanf("%d%d", &r, &c);
	for(int i = 1; i <= r; i++) scanf("%s", mp[i] + 1);
	calc();
	scanf("%d", &n);
	for(int i = 1, height; i <= n; i++)
	{
		scanf("%d", &height);
		height = r - height + 1;
		goal(height, (i & 1)? 1: -1);
//		puts("begin:");
//		for(int ii = 1; ii <= r; ii++) puts(mp[ii] + 1);
//		puts("end.");
	}
	for(int i = 1; i <= r; i++) puts(mp[i] + 1);
	return 0;
}