bfs专题

迷宫与陷阱

题目意思：

有一个NxN个格子组成的迷宫，里面的道路用'.'表示，表示可以通过的路，障碍物用'#'表示，表示不能走的路，陷阱用'X'表示，只有无敌的时候才能走过；有的格子还有一种道具，道具用'%'表示，当你第一次到达该格子的时候才能获得无敌时间，能支持你走长度为k的路程（相邻两点之间路程为1），你要从(0,0)出发到达(n-1,n-1)，题目要你求最短的路程.()

题解：

考虑一种情况：当你必须拿道具才能到达终点的时候，你可能需要走回头路，比如你去道具格子，发现除了回头都不能走，这个时候就必须走回头了
如下图：
...##.
...%.#
XXX##
.....
这种情况是需要回头的，那怎么办呢？我们要区分一下这种情况，我们不能直接判断走过的路就不能走了，我们可以给vis数组加一维，vis[x][y][z]表示在位置(x,y)且无敌状态为z时是否走过，走过就不能再走了，只有去获得无敌道具的时候才能重复走.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 100019;
const int N=1005,M = 1<<21;
inline ll read()
{
    ll st = 0, w = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            w = -1;
    for (; isdigit(ch); ch = getchar())
        st = (st << 1) + (st << 3) + (ch ^ 48);
    return st * w;
}
int dir[4][2] = {{0,1} , {0,-1} , {1,0} , {-1,0}};
int n , k;
bool vis[N][N][11];//该题可以走回头路，因为有的时候可能需要拿道具过陷阱
bool check(int x,int y){
    if(x >= 0 && x < n && y >= 0 && y < n) return true;
    return false;
}
struct node{
    int x,y,step,k;
    node(int a,int b,int c ,int d){
        x = a,y = b, step = c,k = d;
    }
};
string mp[N];
int bfs(){
    queue<node>q;
    q.push(node{0,0,0,0});
    vis[0][0][0] = 1;
    while(q.size()){
        node ed = q.front();q.pop();
        if(ed.x == n - 1 && ed.y == n - 1){
            return ed.step;
        }
        for(int i = 0 ; i < 4; i++){
            int dx = ed.x + dir[i][0];
            int dy = ed.y + dir[i][1];
            if(check(dx,dy) && mp[dx][dy] != '#'){
                if(mp[dx][dy] == '%' && !vis[dx][dy][k]){
                   vis[dx][dy][k] = 1;
                   q.push(node{dx,dy,ed.step + 1,k});
                }
                if(ed.k && !vis[dx][dy][ed.k - 1]){//当前无敌
                    vis[dx][dy][ed.k - 1] = 1;
                    q.push(node{dx,dy,ed.step + 1,ed.k - 1});                    
                }
                else if(mp[dx][dy] == '.' && !vis[dx][dy][0]){
                    vis[dx][dy][0] = 1;
                    q.push(node{dx,dy,ed.step + 1,0});
                }
            }
        }
    }
    return -1;
}
int main()
{
    n = read() , k = read();
    for(int i = 0; i < n ; i++)  cin>>mp[i];
    cout<<bfs()<<endl;
    return 0;
}