迷宫与陷阱--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;
}