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

· · 题解

思路

题目要求在地图中寻找满足要求的最短路径，可以用 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;
}

点个赞再走吧！