P9425 [蓝桥杯 2023 国 B] AB 路线

一、问题简析

本题是一道 \(BFS\) 题。与普通的广搜题不同的是，本题中，格子可以多次访问。因此，vis 数组不能只用二维，要进行升维。

本题中，每个节点包含以下信息：

struct node
{
    pair<int, int> loc;     // 坐标
    char ch;                // 格子的值（A或B）
    int cnt;                // 累计经过A或B的个数
    int step;               // 累计步数
};

在普通深搜题中，我们令 vis[x][y] 表示坐标 (x, y) 是否访问过。若未访问，且满足一定条件，则更新节点，并加入队列。由于题意的限制，更新后的节点一定满足 1 <= node.cnt <= K。这就表明，在坐标 (x, y) 更新后的节点有 K 种可能的状态。在普通的深搜题的要求下——每个坐标只能访问一次，只能是 K 种状态中的一种。然而，在允许多次访问的题目中，需要考虑这 K 种状态。

回到本题，我们令 vis[x][y][k] 表示在坐标 (x, y) 处，更新后，是否有过节点 node.cnt == k。若没有，且满足一定条件，则更新节点，并加入队列。更新条件为：
设未更新前的节点为 bf; 下一个坐标为 (x, y)（合法的）; 表示的字符为 A[x][y]。

if A[x][y] == bf.ch
    if bf.cnt < K and !vis[x][y][bf.cnt + 1]
        // ... 更新节点
        vis[x][y][bf.cnt + 1] = true
else
    if bf.cnt == K and !vis[x][y][1]
        // ... 更新节点
        vis[x][y][1] = true

注：因为 1 <= node.cnt <= K，所以 vis 数组的第三维要比 K 大。

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

typedef pair<int, int> P;
struct node{P loc; char ch; int cnt, step;};

int N, M, K;
char A[1005][1005];
bool vis[1005][1005][15];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool check(P p)
{
	int x = p.first, y = p.second;
	if (1 <= x && x <= N && 1 <= y && y <= M)
		return true;
	return false;
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	cin >> N >> M >> K;
	for (int i = 1; i <= N; ++i)
	{
		char ch = getchar();
		while (ch != '\n')
			ch = getchar();
		
		for (int j = 1; j <= M; ++j)
			A[i][j] = getchar();
	}
	
	queue<node> Q;
	Q.push(node{P(1, 1), 'A', 1, 0});
	vis[1][1][1] = true;
	while (!Q.empty())
	{
		node bf = Q.front();
		Q.pop();
		P p = bf.loc;
		
		if (p == P(N, M))
		{
			cout << bf.step << endl;
			return 0;
		}
		
		for (int i = 0; i < 4; ++i)
		{
			int x = p.first + dx[i], y = p.second + dy[i];
					
			if (!check(P(x, y)))    continue;
			
			if (A[x][y] == bf.ch)
			{
				if (bf.cnt < K && !vis[x][y][bf.cnt + 1])
				{
					Q.push(node{P(x, y), bf.ch, bf.cnt + 1, bf.step + 1});
					vis[x][y][bf.cnt + 1] = true;
				}
			}
			else
			{
				if (bf.cnt == K && !vis[x][y][1])
				{
					Q.push(node{P(x, y), A[x][y], 1, bf.step + 1});
					vis[x][y][1] = true;
				}
			}
		}
	}
	
	cout << -1 << endl;
	
	return 0;
}

完