这道题是真有意思，感觉有点难度，这个不能用简单的二维数组v判重，要用三维v判重，
v[i][j][k] 走到 i 行 j 列的且无敌状态还有 k步 的 时候是否以前有过这种情况；
#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 ; }
