链接：https://ac.nowcoder.com/acm/contest/102896/F
来源：牛客网

题目描述（简化）

有一个 n 行 m 列的二维垂直网格迷宫，我们使用 (i,j) 表示网格中从上往下数第 i 行和从左往右数第 j 列的单元格。每个方格要么是空方格 ‘.’，要么是障碍物方格 ‘#’。特别的，迷宫的边缘外视作无法被摧毁的边界。
每一个障碍物的初始耐久均为 h。方向向下的水流如果接触到障碍物，会使其下方的障碍物每秒损失 1 点耐久。当耐久为 0 时，再次造成耐久损失，则视为摧毁该障碍物。摧毁后，障碍物的位置在下一秒起可通行。
起点的水流（用 ‘*’ 表示），水的任意部分每秒都会扩散一个单位长度，规则如下：
在下方存在障碍物时，水流同时向左、右两侧流动。
在下方无障碍物时，水流只能向下流动。
水流路径交叉时，比如在扩散产生的水平水流上方存在一条向下流动的垂直水流，则多条路径均会生效（在本案例中，垂直水流也会使下方障碍物耐久损失），而不对原有的水平水流产生影响。但同一方向的水流产生的效果不会叠加。
已存在的水流不会消失。在迷宫边界外不存在障碍物等实体，水流流出边界视作消失。
问水流最短经过多久可以抵达终点（使用 ‘%’ 表示）。如果水流无法抵达终点，输出 −1

题目类型

有限制的BFS（分类讨论）+三维vis

思路

遇到迷宫问题，又是求最短路径，考虑一下BFS
对于BFS，可以采用队列与优先队列，此处采用优先队列，排序依据是time从小到大
关键点（对于障碍物的解读与转化）（P.S.:当时赛时没想到障碍物的转化方式，现在想想真是唐完了）
对于障碍物而言，其具有h的耐久-->竖直状态的水流在它的上面一格必须停留h秒，第h+1秒才能往下走一格-->往下走一格的time为上一格的time+h+1（把下面那一格push进优先队列）
在下方存在障碍物时，水流同时向左、右两侧流动-->如果在下方存在障碍物时，水流的左边没有障碍物，则把左边那一格push进优先队列， 右边没有障碍物，则把右边那一格push进优先队列。
这样子最关键的部分就分类讨论完了，下面考虑如何防止死循环，最经典的是用vis数组
所以一种想法是开一个vis[N][M]数组，记录某一个格子是否被经过，如果已经被经过就无需再次经过
但是这样真的对吗？
同一个格子，它既可能被水平状态的水流通过，又可能被竖直状态的水流通过，难道一个格子如果被水平状态的水流通过，就不能被竖直状态的水流通过了吗？
答案是否定的，因为可能会出现竖直水流穿过水平水流的情况，这个时候让竖直水流无法通过肯定是不对的
但是可以发现，对于每一个格子，其最多可以被竖直水流穿过1次，同时最多可以被水平水流穿过1次。
所以考虑开三维vis[N][M][2]数组，其中vis[N][M][0]记录是否被竖直状态的水流穿过，vis[N][M][1]记录是否被水平状态的水流穿过
为了方便，可以在优先队列里面存储水流的状态（0：竖直，1：水平）
其他部分就和普通的BFS差不多了

代码 

#include<bits/stdc++.h>
#define int long long int
using namespace std;
const int N=1e3+20;
string mp[N];
int vis[N][N][2];
int n,m,h,ans=1e18;
struct node{
	int x,y,tim,zt; //zt:0:竖直 1:水平 
	bool operator<(const node& y) const{
        return y.tim < tim;
    }
};
priority_queue<node>que;

void BFS(){
	while(!que.empty()){
		node tmp=que.top();
		que.pop();
		if(tmp.x<0 || tmp.y<0 || tmp.x>=n || tmp.y>=m || vis[tmp.x][tmp.y][tmp.zt]) continue;
		vis[tmp.x][tmp.y][tmp.zt]=1;
		if(mp[tmp.x][tmp.y]=='%'){
			ans=tmp.tim;
			return ;
		}
		if(tmp.x+1<n && mp[tmp.x+1][tmp.y]=='#'){
			if(tmp.y-1>=0 && mp[tmp.x][tmp.y-1]!='#') que.push(node{tmp.x,tmp.y-1,tmp.tim+1,1});
			if(tmp.y+1<m && mp[tmp.x][tmp.y+1]!='#') que.push(node{tmp.x,tmp.y+1,tmp.tim+1,1});
			if(tmp.zt==0) que.push(node{tmp.x+1,tmp.y,tmp.tim+h+1,0});
		}else{
			que.push(node{tmp.x+1,tmp.y,tmp.tim+1,0});
		}
	}
}

signed main(){
	cin>>n>>m>>h;
	for(int i=0;i<n;i++){
		cin>>mp[i];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(mp[i][j]=='*'){
				que.push(node{i,j,0,0});
				BFS();
				if(ans!=1e18) cout<<ans<<endl;
				else cout<<"-1"<<endl;
				return 0;
			}
		}
	}
	return 0;
}