P9425 [蓝桥杯 2023 国 B] AB 路线(bfs)

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int mod=1e9+7;
4. int dx[4]={-1,0,0,1};
5. int dy[4]={0,-1,1,0};
6. typedef pair<int,int> pii;
7. #define int long long
9. const int N=1010;
11. struct node{
12.         int x,y,d;
13. };
14. char g[N][N];
15. int n,m,k;
16. int st[N][N][20];
18. void solve()
19. {
20.         cin>>n>>m>>k;
21.         for(int i=1;i<=n;i++)
22.         {
23.                 for(int j=1;j<=m;j++)cin>>g[i][j];
24.         }       
25.         st[1][1][1]=1;
26.         queue<node>q;
27.         q.push({1,1,0});
28.         int flag=0;
29.         while(q.size())
30.         {
31.                 auto t=q.front();
32.                 q.pop();
33.                
34.                 int x=t.x,y=t.y,d=t.d;
35.                 if(x==n&&y==m)
36.                 {
37.                         flag=1;
38.                         cout<<d<<endl;
39.                         return;
40.                 }
41.                 for(int i=0;i<4;i++)
42.                 {
43.                         int a=dx[i]+x,b=dy[i]+y;
44.                         int dd=(d+1)%(k*2);
45.                         char ch;
46.                         if(dd>=0&&dd<k)ch='A';
47.                         else ch='B';
48.                         if(a>=1&&a<=n&&b>=1&&b<=m&&g[a][b]==ch&&st[a][b][(d+1)%k]==0)
49.                         {
50.                                 st[a][b][(d+1)%k]=1;
51.                                 q.push({a,b,d+1});
52.                         }
53.                 }
54.         }
55.         if(flag==0)cout<<"-1"<<endl;
56. }
57. signed main()
58. {
59.     int good_luck_to_you;
60.     ios::sync_with_stdio(false);
61.     cin.tie(0);
62.     cout.tie(0);
63.     good_luck_to_you=1;
64.     //cin>>good_luck_to_you;
65.     while(good_luck_to_you--)
66.     {
67.        solve();
68.     }
69.     return 0;
70. }

复制代码

  本道题和平凡的bfs板子题不一样，它是一个格子可以走很多次，这里的话一个格子走的不能高出k次，所以我们在st数组又加了一维，表示这个格子不能走的高出k次，其他的和模板是一样的。 
   


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。