自动搬运

查看原文

来自洛谷，原作者为

	DreamLand_zcb 此生无悔入MC，来世还做方块人！

搬运于2025-08-24 22:41:31，当前版本为作者最后更新于2023-05-02 20:43:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

简要题意

占地 $5 \times 5$ 的小明从 $n \times n$ 的迷宫的 $(3, 3)$ 走到 $(n-2, n-2)$。并且当到达时刻 $k$ 的时候小明占地变成 $3 \times 3$，在时刻 $2 \times k$ 的时候占地变成 $1 \times 1$。小明每次可以选择向上下左右四个方向走动，每次走动用时 $1$ 个时刻，当然也可以选择站着不动。

求小明到达终点时的时刻。

思路

类似于求最短路径的问题，可以使用 bfs 讨论。

定义队列 $q$，含有四个元素：

• $x$ 和 $y$：当前小明坐标

• $Time$：当前时刻

• $size$：小明身材

每次取出队首并向四个方向以及不动拓展，并判断当前位置是否走过以及这个位置小明能否站的下（小明的占地区域内有没有障碍物），如果站的下就入队，入队时判断一下小明身材的情况。

判断的时候有个小优化，及当小明占地是 $1 \times 1$ 的时候可以不用判断小明原地不动的情况，此时站着不动是无意义的举措，因为无论怎样走都不会有障碍物遮挡他。

代码

#include <bits/stdc++.h>
#define ll long long
#define setp setprecision
#define mem(a, m) memset(a, m, sizeof(a));
using namespace std;

int n, k;
int ans = 0x3f3f3f;
int a[305][305];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool vis[305][305];
struct node {
	int x, y;//坐标
	int Time;//时间
	int size;//小明大小 
};
bool check(int x, int y, int size)
{
	if(vis[x][y])	return false;
	for(int i=x-size;i<=x+size;i++)
		for(int j=y-size;j<=y+size;j++)
			if(i < 1 || i > n || j < 1 || j > n || a[i][j])
				return false;
	return true;
}
int work(int Time)
{
	if(Time < k)	return 2;
	else if(Time < 2 * k)	return 1;
	else	return 0;
}
void bfs()
{
	queue <node> q;
	vis[3][3] = 1;
	q.push((node){3, 3, 0, 2});
	while(!q.empty())
	{
		node t = q.front();
		q.pop();
		if(t.x == n - 2 && t.y == n - 2)//到达终点，停止搜索 
		{
			cout << t.Time;
			return ;
		}
		if(t.size != 0)	q.push((node){t.x, t.y, t.Time+1, work(t.Time+1)});//站着不动
		for(int i=0;i<4;i++)
		{
			int X = t.x + dx[i];
			int Y = t.y + dy[i];
			if(check(X, Y, t.size))//判断
			{
				vis[X][Y] = 1;
				q.push((node){X, Y, t.Time+1, work(t.Time+1)});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			char c;
			cin >> c;
			if(c == '*')	a[i][j] = 1;
			else	a[i][j] = 0;
		}
	}
	bfs();
	return 0;
}