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;
}