P3818 小A和uim之大逃离 II 题解

### 1. 题意解释

给出一个 $H$ 行 $W$ 列的迷宫，你可以往上下左右移动一格或喝魔药移动 $D$ 行 $W$ 列，求最少需要多少次才能逃出迷宫。

### 2. 思路

怎么其他人都写 BFS，就我一个分层图最短路是吧……

由于魔药只能喝一次，所以我们建两次图，对于两个相同的点，我们用边权为 $0$ 的边将其相连。

如果我们在同一层跑最短路，也就是不喝魔药时所需的最短路径。

问题来了：如何处理喝了魔药的情况？

由于我们刚才建了两层图，所以我们可以把第一层的 $(i,j)$ 点与第二层的 $(i+D,j+R)$ 点相连，表示喝了一次魔药后位于 $(i+D,j+R)$ 点。

只需要跑从第一层的 $(1,1)$ 到第二层的 $(H,W)$ 的最短路就好了。

### 3. 代码实现

进食后人：数组一定要开大！不然第二个点会 WA！

```cpp
#include<bits/stdc++.h>
using namespace std;
int h,w,d,r,head[4000400],tot=1,dist[4000400],vis[4000400];
char ch[2020][2020];
deque<int>q;
struct data{
	int nxt,to,w;
}edge[32003200];
int get(int x,int y){
	return (x-1)*w+y;
}
void spfa(int s){
	memset(dist,0x3f,sizeof dist);
	memset(vis,0,sizeof vis);
	dist[s]=0;
	vis[s]=1;
	q.push_back(s);
	while(!q.empty()){
		int x=q.front();
		q.pop_front();
		vis[x]=0;
		for(int i=head[x];i;i=edge[i].nxt){
			int y=edge[i].to;
			if(dist[x]+edge[i].w<dist[y]){
				dist[y]=dist[x]+edge[i].w;
				if(!vis[y]){
					if(!q.empty()&&dist[y]>=dist[q.front()]){
						q.push_back(y);
					}
					else{
						q.push_front(y);
					}
					vis[y]=1;
				}
			}
		}
	}
}
void add(int u,int v,int w){
	edge[tot].nxt=head[u];
	edge[tot].to=v;
	edge[tot].w=w;
	head[u]=tot++;
}
signed main(){
	cin>>h>>w>>d>>r;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>ch[i][j];
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(ch[i][j]=='.'){
				add(get(i,j),h*w+get(i,j),0);
				if(ch[i][j+1]=='.'&&j+1<=w){
					add(get(i,j),get(i,j+1),1);
					add(h*w+get(i,j),h*w+get(i,j+1),1);
				}
				if(ch[i][j-1]=='.'&&j-1>=1){
					add(get(i,j),get(i,j-1),1);
					add(h*w+get(i,j),h*w+get(i,j-1),1);
				}
				if(ch[i+1][j]=='.'&&i+1<=h){
					add(get(i,j),get(i+1,j),1);
					add(h*w+get(i,j),h*w+get(i+1,j),1);
				}
				if(ch[i-1][j]=='.'&&i-1>=1){
					add(get(i,j),get(i-1,j),1);
					add(h*w+get(i,j),h*w+get(i-1,j),1);
				}
				if(ch[i+d][j+r]=='.'&&i+d<=h&&j+r<=w&&i+d>=1&&j+r>=1){
					add(get(i,j),h*w+get(i+d,j+r),1);
				}
			}
		}
	}
	spfa(1);
	if(dist[2*h*w]!=0x3f3f3f3f){
		cout<<dist[2*h*w];
	}
	else{
		cout<<-1;
	}
	return 0;
}
```

正在渲染内容...