迷宫与陷阱--bfs+回路+剪枝

1.用bfs板子，同时会出现回路，但不能不用bo数组，要减去一部分没有用的回路

2.什么叫没有用的回路--因为我有无敌了，以前遇到的陷阱就能过了，那这就是有用的回路，

所以我记录（x,y）点的无敌状态步数（初始化为0），如果回来的步数大于之前的，那么很·有用，因为可能会过一些陷阱，如果小于等于那就纯纯浪费时间

P8673 [蓝桥杯 2018 国 C] 迷宫与陷阱 - 洛谷

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<int,int> pii;
int n,k;
char a[1005][1005];
int bo[1005][1005];
int kk[1005][1005];
int an=0x3f3f3f3f;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
struct no
{int x,y,w;
};
queue<no> q;
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) cin>>a[i][j];}bo[1][1]=1;q.push({1,1,0});while(q.size()){no t=q.front();q.pop();int x=t.x,y=t.y;if(x==n&&y==n){cout<<bo[x][y]-1;return 0;}if(bo[x][y]>=n*n-1){cout<<-1;return 0;}for(int i=0;i<4;i++){int tx=x+dx[i],ty=y+dy[i];if(tx>=1&&tx<=n&&ty>=1&&ty<=n){if(!bo[tx][ty]){if(a[tx][ty]=='.'){bo[tx][ty]=bo[x][y]+1;q.push({tx,ty,max(t.w-1,0)});}if(a[tx][ty]=='%'){bo[tx][ty]=bo[x][y]+1;kk[tx][ty]=k;q.push({tx,ty,k});a[tx][ty]='.';}if(a[tx][ty]=='X'&&t.w>0){bo[tx][ty]=bo[x][y]+1;kk[tx][ty]=t.w-1;q.push({tx,ty,t.w-1});}	}else///最关键的一步，采用有用的回路 {if(a[tx][ty]=='%'&&k>kk[tx][ty]){bo[tx][ty]=bo[x][y]+1;kk[tx][ty]=k;q.push({tx,ty,k});a[tx][ty]='.';}if(a[tx][ty]=='X'&&t.w>0&&t.w-1>kk[tx][ty]){bo[tx][ty]=bo[x][y]+1;kk[tx][ty]=t.w-1;q.push({tx,ty,t.w-1});}if(a[tx][ty]=='.'&&max(t.w-1,0)>kk[tx][ty]){bo[tx][ty]=bo[x][y]+1;q.push({tx,ty,max(t.w-1,0)});}}}}}cout<<-1;return 0;
}