[蓝桥杯 2018 国 C] 迷宫与陷阱

题目链接：迷宫与陷阱

这道题目跟我们平时做的bfs不同的是 多了一个“无敌状态” 那么也就需要我们去比较有无敌状态经过陷阱和不走陷阱的最少的步数。

先说说我之前的思路吧：

开一个vis[N][N]表示走到（x,y) 这个点所需最小的步数，

再开一个st[N][N]表示这个无敌状态还能持续多少步，假设%这个点为0，一步步增多，超过k结束

这个思路是正确的，但。。。。

没错，内存超限了。。。

想看原代码的话如下：

 

#include <bits/stdc++.h>
using namespace std;
const int N =1005;
char a[N][N];
int vis[N][N];
int st[N][N];
int n,k,sx,sy,ex,ey;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct node{
	int x,y;
};
 
void bfs(int sx,int sy){
	queue<node>q;
	q.push({sx,sy});
	while(!q.empty()){
		int x=q.front().x;
		int y=q.front().y;
		q.pop();
		for(int i=0;i<4;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx<1||nx>n||ny<1||ny>n)continue;
			if(a[nx][ny]=='#')continue;
			if(vis[nx][ny]<0x3f/2&&st[nx][ny]<st[x][y])continue;
			if(st[x][y]>k-1&&a[nx][ny]=='X')continue;
			st[nx][ny]=min(st[nx][ny],st[x][y]+1);
			vis[nx][ny]=vis[x][y]+1;
			q.push({nx,ny});
		}
	}
}
 
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	sx=sy=1;
	ex=ey=n;
	memset(vis,0x3f,sizeof(vis));
	memset(st,0x3f,sizeof(st));
	vis[sx][sy]=0;
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		for(int j=1;j<=n;j++){
			a[i][j]=s[j-1];
			if(a[i][j]=='%'){
				st[i][j]=0;
			}
		}
	}
 
	if(a[sx][sy]=='.')bfs(sx,sy);
 
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			cout<<vis[i][j]<<" ";
//		}
//		cout<<"\n";
//	}
 
	if(vis[ex][ey]==0x3f)cout<<-1<<"\n";
	else cout<<vis[ex][ey]<<"\n";
 
	return 0;
}

那么怎么考虑将这个无敌状态伴随着呢？那么我们可以考虑将这个状态放到struct结构体里面，因为queue中提取的x，y就是我要遍历的这个点，所以当前的状态就正好可以表示，那么同样我也可以将步数塞进去，那么此时就少了st数组，那么vis数组的作用在于记录当前这个点的无敌状态。

为什么还要用vis记录无敌状态呢？

这就考虑到跟上一个点比较了，原本的图遍历我们只需走一次即可，那么出现了新的无敌状态就要考虑我是不是可以先去拿这个无敌状态然后往回走再去走陷阱呢？

5 3
...XX
##%#.
...#.
.###.
.....

就如例题这个，那么就要回溯，回溯的条件就是当前的无敌值一定是比我要去的无敌值大。

因为不可能走比自己无敌值小的点（遍历过的点）

代码附上：

#include <bits/stdc++.h>
using namespace std;
const int N =1005;
char a[N][N];
int vis[N][N];//走到该点的无敌步数多少
int n,k,sx,sy,ex,ey;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct node{
	int x,y,w,st;
};
bool flag=false;
 
void bfs(int sx,int sy){
	queue<node>q;
	q.push({sx,sy,0,0});
	vis[sx][sy]=0;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.x==ex&&t.y==ey){
			flag=true;
			cout<<t.st<<"\n";
			return;
		}
		for(int i=0;i<4;i++){
			int nx=t.x+dx[i];
			int ny=t.y+dy[i];
			if(nx<1||nx>n||ny<1||ny>n)continue;
			if(a[nx][ny]=='#')continue;
			if(t.w==0&&a[nx][ny]=='X')continue;
			int w=max(0,t.w-1);//计算目前的无敌值
			if(a[nx][ny]=='%'){
				w=k;
			}//2 1 0
			if(vis[nx][ny]>=w)continue;//回溯的条件
			vis[nx][ny]=w;
			q.push({nx,ny,w,t.st+1});
		}
	}
}
 
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	sx=sy=1;
	ex=ey=n;
	memset(vis,-1,sizeof(vis));
	vis[sx][sy]=0;
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		for(int j=1;j<=n;j++){
			a[i][j]=s[j-1];
		}
	}
 
	if(a[sx][sy]=='.')bfs(sx,sy);
 
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			cout<<vis[i][j]<<" ";
//		}
//		cout<<"\n";
//	}
 
	if(!flag)cout<<-1<<"\n";
 
	return 0;
}