蓝桥杯2018年第九届真题-迷宫与陷阱 BFS

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define endl '\n'
const ll N=1e3+5;
struct node{
    ll x,y;
    ll tp,sp;//tp表示步数，sp表示可以无敌的步数；
};
ll n,k,kkk;
ll dx[]={0,0,-1,1};
ll dy[]={-1,1,0,0};
char a[N][N];
ll vis[N][N];
void bfs(){
    queue<node> q;
    q.push({1,1,0,0});
    while(q.size()){
       node t=q.front();q.pop();
        //cout<<t.sp<<endl;
       if(t.x==n&&t.y==n){
          kkk=1;
          cout<<t.tp<<endl;
          return;
       }
       for(ll i=0;i<4;i++){
          ll xx=t.x+dx[i];
          ll yy=t.y+dy[i];
          if(xx<1||xx>n||yy<1||yy>n)continue;
          if(a[xx][yy]=='#')continue;
            if(vis[xx][yy]>=t.sp)continue;//小于已记录的无敌步数则跳过,因为无敌步数越多越好
          if(t.sp==0&&a[xx][yy]=='X')continue;
            ll spp=max((ll)0,t.sp-1);
            if(a[xx][yy]=='%')spp=k;
            vis[xx][yy]=spp;
            q.push({xx,yy,t.tp+1,spp});
       }
    }
}
int main(){
    cin>>n>>k;
    memset(vis,-1,sizeof vis);
    for(ll i=1;i<=n;i++){
       for(ll j=1;j<=n;j++){
          cin>>a[i][j];
       }
    }
    bfs();
    if(!kkk)cout<<-1<<endl;
    return 0;
}