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

~~应该能过官方数据吧~~

---

回归正题。我开始想过更简单的深搜，但是我怕无法记忆化，所以选择了广搜。和普通的广搜不同，此题的队列要存 $3$ 个维度，分别是 $x$，$y$，$z$，分别表示横坐标、纵坐标、目前的步数模 $2k$ 的值。

此时我们可以把每 $2k$ 步进行分组，前 $k$ 步走在 ```A``` 的格子上，后 $k$ 步走在 ```B``` 的格子上。

这里的每一步都要分类讨论，以下记 $a$ 为下一步模 $2k$ 的值。

- 当 $a \ge k$ 时，下一步必须走在 ```B``` 的格子上。

- 否则，下一步必须走在 ```A``` 的格子上。

然后就做完了。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,k,x,y,z,nx,ny,nz;
int dis[N][N]; 
char mp[N][N];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
queue< pair< pair<int,int> ,int> >q; //用queue记三维信息
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1; i<=n; i++) scanf("%s",mp[i]+1);
    if(mp[1][1]!='A'){
        puts("-1");
        return 0;
    }
    memset(dis,0x3f,sizeof dis);
    dis[1][1]=0;
    q.push({{1,1},0});
    while(!q.empty()){
        x=q.front().first.first;
        y=q.front().first.second;
        z=q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            nx=x+dx[i],ny=y+dy[i],nz=(z+1)%(2*k);
            if(nx<1 || nx>n || ny<1 || ny>m) continue;
            if(nz<k && mp[nx][ny]=='B') continue;
            if(nz>=k && mp[nx][ny]=='A') continue;
            if(dis[nx][ny]>dis[x][y]+1){
                dis[nx][ny]=dis[x][y]+1;
                q.push({{nx,ny},nz});
            }
        }
    }
    if(dis[n][m]==dis[0][0]) puts("-1");
    else printf("%d\n",dis[n][m]);
    return 0;
}