P9425 [蓝桥杯 2023 国 B] AB 路线(无结构体+取模判断+详细注释版)

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

蚌

是分层图BFS,但一开始想取巧不写分层图,结果60分,老老实实写分层图(YvY)

思路

题目中要求先k个A,再k个B,如此往复,除最后一组中可以不足k个

题目中k的范围不大,         没有说明一个点只能走一次,

相当于每个点有k个状态(即每个点离散的可以出现在组中的1、2、...、k位置上)

所以我们给vis加一个纬度,存点的1-k的状态

接下来处理当前要走A还是B的问题,我们给路径字符串从0开始加下标,因为我们是从A开始走

我们可以发现 合法字符串中 A字符的下标 除 k 的 (int)值永远为偶数 , B字符的下标 除 k 的值永远为奇数

EG:

AAABBBAA k=3

01234567(可以自行验证

那么多加一个cnt[][]来存当前点的下标即可完成对需要A还是B的判断

AC代码

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

//#define int long long

int n,m,k;
char mp[1003][1003]; //存地图
bool vis[1003][1003][11]={false}; //存点的1-k个状态有没有被走过
int cnt[1003][1003]; //存当前点走的是第几步
string s;
int dx[4]={0,1,0,-1}; //两个方向数组
int dy[4]={1,0,-1,0};

void bfs(){
    queue<pair<int,int> > q;
    pair<int,int> p;
    int x,y,px,py; //当前xy与下一步的xy
    q.push({1,1}); //放入起点
    vis[1][1][0]=true; //起点为第0步
    while(!q.empty()){
        p=q.front(); q.pop();
        x=p.first; y=p.second;
        if(x==n && y==m){  //走到终点了就结束
            cout<<cnt[x][y];
            return ;
        }
        int aa = cnt[x][y]+1; //下一步是第几步
        int bb = (aa/k)%2; //看除k是偶数还是奇数
        if(bb==0){ //偶数表示需要字符 A
            for(int i=0;i<4;++i){
                px=x+dx[i]; py=y+dy[i];
                if(px>=1 && px<=n && py>=1 && py<=m && !vis[px][py][aa%k] && mp[px][py]=='A'){ //不要换序,越界会RE
                        cnt[px][py]=cnt[x][y]+1;
                        vis[px][py][aa%k]=true; //标记该点的当前状态
                        q.push({px,py});
                }
            }
        }
        else{ //奇数表示需要字符 B
            for(int i=0;i<4;++i){
                px=x+dx[i]; py=y+dy[i];
                if(px>=1 && px<=n && py>=1 && py<=m && !vis[px][py][aa%k] && mp[px][py]=='B'){
                        cnt[px][py]=cnt[x][y]+1;
                        vis[px][py][aa%k]=true;
                        q.push({px,py});
                }
            }
        }
    }
    cout<<-1; //走不到就输出-1
}

void solve(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i){
        cin>>s;
        for(int j=1;j<=m;++j) mp[i][j]=s[j-1]; //字符串拆字符建图
    }
    bfs();
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int _=1;
    //cin>>_;
    while(_--){
        solve();
    }
    return 0;    
}