[蓝桥杯] AB路线

蜡笔小浩CrayonTech

478人浏览 · 2025-03-06 22:57:31

蜡笔小浩CrayonTech · 2025-03-06 22:57:31 发布

蓝桥账户中心

题意

给定n*m的迷宫由A,B组成从左上角出发走到右下角

有个特殊的限制每次必须走k个A 然后再走k个B 再走k个A...最后一段A或B的格子可以走少于k格

左上角保证为A 求最少步数

思路

[蓝桥杯]真题讲解：AB路线（BFS+分层图）_哔哩哔哩_bilibili

题解来自bilibili Turing_Sheep

1≤N,M≤1000，1≤K≤10

bfs就可以找到最短路

不同点

这里与普通的bfs不同这道题是可能重复走一个点的

比如

A必须走五次所以一定会重复走A点

发现

k=3

1 2 3 4 5 6

A A A B B B

第i个点： i/k为偶数说明下一个点i+1是A

i/k为奇数说明下一个点i+1是B

所以bfs时记录每个点的dis 表示是第几个点而不是记录里起点的最短距离

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);}
void cmin(int &a,int b){a=min(a,b);}
const int N=1010,MOD=1e9+7,INF=0x3f3f3f3f,LINF=LLONG_MAX;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int n,m,k;
int dis[N][N][20];
int g[N][N];
bool st[N][N][20];

int bfs(){

    queue<ar3>q;
    q.push({1,1,1});
    st[1][1][1]=1;

    while(q.size()){
        auto [x,y,cnt]=q.front();q.pop();
        int d=dis[x][y][cnt];//第d个点

        for(int i=0;i<4;i++){
            int tx=x+dx[i],ty=y+dy[i];
            int c=(d/k)%2;//余0表示下一个为A 余1表示下一个为B
            if(tx<1||tx>n||ty<1||ty>m) continue;
            if(c==g[tx][ty]&&!st[tx][ty][(d+1)%k]){
                st[tx][ty][(d+1)%k]=1;
                dis[tx][ty][(d+1)%k]=d+1;
                q.push({tx,ty,(d+1)%k});
            }
        }
    }
    int res=INF;
    for(int i=0;i<k;i++){
        cmin(res,dis[n][m][i]);
    }
    return res;
}
void solve() {
    cin>>n>>m>>k;
    memset(dis,0x3f,sizeof dis);
    dis[1][1][1]=1;

    for(int i=1;i<=n;i++){
        string s;cin>>s;
        for(int j=1;j<=m;j++){
            g[i][j]=s[j-1]=='B';
        }
    }

    int res=bfs();
    if(res==INF){
        cout<<-1<<endl;
    }else{
        cout<<res-1<<endl;
    }
}   

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t=1;
    // cin>>t;
    while (t--) solve();

}

dis 和 st开三维第三维表示这个字母在这一小段是第几个

第三维其实是[0,k-1] 因为(d+1)%k之后如果d+1==k 会被表示成0 但其实意思是第k个这样只是方便处理

另外 (d+1)%k是什么意思？

也可以写成(cnt+1)%k 同样可以通过上一个的编号推出这个点的组内编号

如果上一个点是第k个点也就是cnt=0 那么这个点就是本组的第一个点 cnt+1 刚好是1

        int id=(cnt+1)%k;
        if(c==g[tx][ty]&&!st[tx][ty][id]){
                st[tx][ty][id]=1;
                dis[tx][ty][id]=d+1;
                q.push({tx,ty,id});
        }

(d+1)%k的解释：

当前这个点(tx,ty)是走过的第d+1个点前面都是k个一组 k个一组的

对k取模就可以得到这个点在自己这一组是第几个