自动搬运

查看原文

来自洛谷，原作者为

	lym2022 这个人很勤快，但不想留下什么

搬运于2025-08-24 22:48:15，当前版本为作者最后更新于2025-05-12 15:45:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

题目要求在地图中寻找满足要求的最短路径，可以用 bfs 来解决。

从左上角开始走，每次遍历周围的四个格子，如果在地图内，并且走了不会违反题目所要求的交替走，并且没有走过，那就将该格子入队。直到走到右下角或者队列为空。

具体的：可以开一个结构体队列，结构体里存 $4$ 个值，当前坐标 $x,y$，一共走的步数 $step$，以及走当前的字母已经走了几个 $s$。在每次取出队头后，判断 $s$ 和 $k$ 相不相等，如果相等说明不能再走这个字母了，下一步需要更换字母，不相等说明必须继续走这个字母。

为了避免重复入队，可以开一个三维数组 $vis_{i,j,l}$，表示坐标为 $i,j$ 的且走到第 $l$ 个 A/B 的格子有没有被走过，每次取队头时判断一下，如果走过就跳过本次循环。

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5; 

const int dx[4] = {0,-1,0,1}; 
const int dy[4] = {-1,0,1,0};

int n,m,k;

char c[N][N];

bool vis[N][N][15];

struct node {
	int x,y,step,s;
};

void bfs() {
	queue<node> q;
	q.push({1,1,0,1});  //将初始情况入队：坐标为 (1,1)，走了 0 步(在初始格子上不算走一步)，在 A/B 上走了 1 个 
	while(!q.empty()) {
		int x = q.front().x;
		int y  = q.front().y;
		int step = q.front().step; 
		int s = q.front().s;
		q.pop(); 
		if(x == n && y == m) {   //如果到右下角了就输出答案，题目规定最后一段 A/B 格子可以不满 k 个 
			cout << step;
			return;
		}
		if(vis[x][y][s]) continue;  //如果走过就跳过 
		vis[x][y][s] = true;        //标记一下 
		if(s == k) {   //当前字母走够了，要换字母 
			for(int i = 0;i<4;i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && c[x][y] != c[nx][ny]) {   //只能将字母不相等的格子入队 
					q.push({nx,ny,step+1,1});  //步数加 1，走过的 A/B 格子初始化为 1 
				}
			}
		}else {  //还没走够 
			for(int i = 0;i<4;i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && c[x][y] == c[nx][ny]) {   //只能将字母相等的格子入队 
					q.push({nx,ny,step+1,s+1});  //步数加 1，走过的 A/B 格子数加 1 
				}
			}
		}
	}
	cout << -1;  //按要求走，走不到，输出 -1 
}

int main() {
	cin >> n >> m >> k;
	for(int i = 1;i<=n;i++) for(int j = 1;j<=m;j++) cin >> c[i][j];
	bfs();
	return 0;
}

点个赞再走吧！