P9425 [蓝桥杯 2023 国 B] AB 路线(bfs)
#include<bits/stdc++.h>using namespace std;
const int mod=1e9+7;
int dx={-1,0,0,1};
int dy={0,-1,1,0};
typedef pair<int,int> pii;
#define int long long
const int N=1010;
struct node{
int x,y,d;
};
char g;
int n,m,k;
int st;
void solve()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)cin>>g;
}
st=1;
queue<node>q;
q.push({1,1,0});
int flag=0;
while(q.size())
{
auto t=q.front();
q.pop();
int x=t.x,y=t.y,d=t.d;
if(x==n&&y==m)
{
flag=1;
cout<<d<<endl;
return;
}
for(int i=0;i<4;i++)
{
int a=dx+x,b=dy+y;
int dd=(d+1)%(k*2);
char ch;
if(dd>=0&&dd<k)ch='A';
else ch='B';
if(a>=1&&a<=n&&b>=1&&b<=m&&g==ch&&st[(d+1)%k]==0)
{
st[(d+1)%k]=1;
q.push({a,b,d+1});
}
}
}
if(flag==0)cout<<"-1"<<endl;
}
signed main()
{
int good_luck_to_you;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
good_luck_to_you=1;
//cin>>good_luck_to_you;
while(good_luck_to_you--)
{
solve();
}
return 0;
} 本道题和平凡的bfs板子题不一样，它是一个格子可以走很多次，这里的话一个格子走的不能高出k次，所以我们在st数组又加了一维，表示这个格子不能走的高出k次，其他的和模板是一样的。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]