lanqiao OJ 229 迷宫与陷阱

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
 
using namespace std ;
const int N = 1100 ;
int n ,k ;
char mp[N][N] ;
int v[N][N][20] ;//这是这道题的关键，v[i][j][k] 走到 i 行 j 列的且无敌状态还有 k步  的 时候是否以前有过这种情况；
int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}} ;
struct node{//记录位置，还可以无敌的步数q，和已经走过的距离u
  int x, y ,q , u ;
  node(int xx, int yy ,int qq , int uu){
    x = xx , y = yy , q = qq, u = uu ;
  }
};
int ans  ;
queue<node> q ; 
bool bfs(){
  q.push(node(0,0,0,0)) ;
  while(!q.empty()){
    node now = q.front() ;
    q.pop() ;
    int x = now.x , y = now.y ;
    if(x == n - 1 && y == n - 1){
      ans = now.u ; return  1 ;
    }
    for(int i = 0 ; i < 4 ; i ++){
      int tx = x + d[i][0] , ty = y + d[i][1] ;
      if(tx<0||tx>=n||ty<0||ty>=n||mp[tx][ty] == '#') continue ;
      if(v[tx][ty][now.q]) continue ;
            //下一步一共有4情况：
            //1.下一步是X,但是无敌状态q==0
            //2.下一步是 . ，怎么样都能走
            //3.下一步是% ，走过去，并且把下一步的 无敌状态q变成k
            //4.下一步是X，并且处于无敌状态
      if(mp[tx][ty] == 'X' && now.q == 0) continue ;
      if(mp[tx][ty] == '.'){
        v[tx][ty][now.q] = 1 ;
        int w = now.q ; 
        if(w) w -- ;
        else  w = 0 ;
        q.push(node(tx,ty,w,now.u+1)) ;
      }
      if(mp[tx][ty] == '%'){
        int w = k ;
        v[tx][ty][now.q] = 1 ;
        q.push(node(tx,ty,w,now.u+1));
      }
      if(mp[tx][ty] == 'X' && now.q){
        v[tx][ty][now.q] = 1 ;
        q.push(node(tx,ty,now.q-1,now.u+1)) ;
      }
    }
  }
  return 0 ;
}
 
int  main(){
  cin >> n >> k ; 
  for(int i = 0 ; i < n ; i++) cin >> mp[i] ;
  v[0][0][0] = 1 ;
  if(bfs()) cout << ans << endl ;
  else cout << -1 << endl ;
  return 0 ;
}