自动搬运

查看原文

来自洛谷，原作者为

	Ashankamiko 。。。

搬运于2025-08-24 21:17:54，当前版本为作者最后更新于2025-05-18 15:39:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目简述

题意

给定一张 $N \times N$ 的地图，地图只包含如下字符。

• 用 @ 表示其中一个玩家的起点。
• 用 # 表示墙，该处不可到达。
• 用 $ 表示计分器，在全局中只能使用一次，但是可以同时使用，优先到达的玩家可以使用，一起到达的要同时使用。
• 用 . 表示路，玩家可以移动到此处，且没有分数。

求玩家最高得到了几分以及所有玩家得到的总分。

思路 1

流程如下。

• 输入地图，如果 $(x,y)$ 为 @，入队。
• 定义 $dis$ 数组，用于储存到达 $(x,y)$ 的最少步数（也可以说是离 $(x,y)$ 最近的起点），并将 $dis$ 的所有元素赋值为极大值。
• 取出队首，设 $r$ 为到达 $(x,y)$ 的最少步数。向四周扩展。如果是 $，并且 $dis$ 仍然为极大值，令 $dis_{tx,ty} \gets r + 1$，入队时使分数加一；如果 $dis$ 不是极大值，判断 $r + 1$ 是否等于 $dis_{tx,ty}$，如果相等，仍然可以获得分数，否则没分。如果是 .，直接入队并且不改变分数。

思路 2

流程如下。

• 输入地图，定义数组 $score$，用于储存有多少个 $ 离 $(x,y)$ 的最近的，也就是当前点扩展后的分数。定义 $maxx$ 和 $ans$ 用于储存最高分数和总分。
• 遍历地图，如果是 $，开始进行广搜。
• 取出队首，设 $r$ 为到达 $(x,y)$ 的最少步数。向四周扩展。如果 $(tx,ty)$ 是 @，并且 $dis_{tx,ty}$ 是极大值，令 $score_{tx,ty} \gets score_{tx,ty} + 1$，如果 $r + 1$ 等于 $dis_{tx,ty}$，也令 $score_{tx,ty} \gets score_{tx,ty} + 1$，如果 $(tx,ty)$ 是 . 入队。在扩展的过程中，需定义标记数组 $vis$，防止重复入队，不过需要注意的是，如果该点为 @，则需无视标记。
• 在广搜过程中，要不断更新 $maxx$，并在广搜结束更新 $ans$。

struct node {
	int x, y; //坐标
    int r; //步数
};
char maps[105][105]; //地图
int dis[105][105]; //最短路径
int number[105][105]; //有几个$离当前点是最近的
int score[105][105]; //分数
queue<node> q;
bool vis[105][105]; //标记数组

在广搜的过程中，如果当前点为 @ 并且可以得到分数，参考以下代码。

if (maps[ux][uy] == '@' && ur <= dis[x][y]) {
    dis[x][y] = ur, number[x][y]++, score[ux][uy]++, maxx = max(maxx, score[ux][uy]);
	continue;
}

最后输出 $maxx$ 和 $ans$ 就可以了。

AC 代码

#include <bits/stdc++.h>
using namespace std;
#define in cin
#define out cout
int n, dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}, maxx, cnt, ans; //基础定义
struct node {
	int x, y, r;
};
char maps[105][105];
int dis[105][105], number[105][105], score[105][105];
queue<node> q;
bool vis[105][105];

void bfs(int x, int y) { //广搜
	memset(vis, 0, sizeof(vis));
	q.push({x, y}), vis[x][y] = true;
	while (!q.empty()) {
		int ux = q.front().x, uy = q.front().y, ur = q.front().r;
		q.pop();
		if (maps[ux][uy] == '@' && ur <= dis[x][y]) { 
			dis[x][y] = ur, number[x][y]++, score[ux][uy]++, maxx = max(maxx, score[ux][uy]);//可以得到分数
			continue;
		}
		for (int i = 0; i < 4; i++) {
			int tx = dx[i] + ux, ty = uy + dy[i];
			if (tx >= 0 && ty >= 0 && tx < n && ty < n && maps[tx][ty] != '#' && !vis[tx][ty])
				q.push({tx, ty, ur + 1}), vis[tx][ty] = true;
		}
	}
	ans += number[x][y];
}
int main() {
	memset(dis, 0x3f, sizeof(dis)); //初始化
	in >> n;
	for (int i = 0; i < n; i++) //输入地图
		for (int j = 0; j < n; j++)
			in >> maps[i][j];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (maps[i][j] == '$')
				bfs(i, j); //对该点进行广搜
	out << maxx << '\n' << ans; //输出答案
	return 0;
}