Znzryb's Blog
0%

D. Drunken Maze（醉迷宫）

Posted on Edited on

思路讲解

这题难点主要就是不要怕，看起来好像很难，但其实就只有16种状态，我还没加快读只跑了171ms。

看了一下大佬的思路，主要就是状态分解，还是分层图的思想。

image

1
2
3
//       y  x  dir dirs
bool vis[N][M][5][5];  
memset(vis, false, sizeof(vis));

所以我们建一个分层状态vis数组，dir指的是方向，dirs指的是在此方向走过的次数

只要vis[][][][]==true我们就continue；

在这个分层图上跑一个bfs

然后注意一下不要撞墙，不要出界，不要dirs>3

AC代码

注意，该写法仅能在C11及以上环境中编译（C98好像没有array）

https://codeforces.com/contest/2041/submission/293790427

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#include <cstring>

using namespace std;
typedef long long ll;
constexpr int dx[]={0,1,0,-1};
constexpr int dy[]={1,0,-1,0};
ll n,m;

// 这题会不会是分层图问题？
// 分不同的层去解决这个问题？
// 先写个bfs
inline bool check(ll x,ll y,vector<vector<char> > &maze){	
// 检查是否出界以及撞墙
	if(y<1 || y>n)
		return false;
	if(x<1 || x>m)
		return false;
	if(maze[y][x]=='#')
		return false;
	return true;
}

int main() {
	cin>>n>>m;
	vector<vector<char> > maze(n+5,vector<char>(m+5)); 
	ll sy=0,sx=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>maze[i][j];
			if(maze[i][j]=='S')
				sy=i,sx=j;
		}
	}
	queue<array<ll, 5>> q;
	//       x,y,step,dir,dirs;
	q.push({sx,sy,0LL,0LL,0LL});
	const ll N=5+static_cast<ll> (n),M=static_cast<ll> (m)+5;
	bool vis[N][M][5][5];  
	memset(vis, false, sizeof(vis));
	ll ans=1e17;
	while (!q.empty()) {
		ll x=q.front()[0];
		ll y=q.front()[1];
		ll step=q.front()[2];
		ll dir=q.front()[3];
		ll dirs=q.front()[4];
		q.pop();
		if(vis[y][x][dir][dirs]){
			continue;
		}
		if(maze[y][x]=='T'){
			ans=min(ans,step);
			continue;
		}
		vis[y][x][dir][dirs]=true;
		for(int i=0;i<4;++i){
			if(i==dir && dirs<3 && check(x+dx[i],y+dy[i],maze))
				q.push({x+dx[i],y+dy[i],step+1,i,dirs+1});
			else if(i!=dir && check(x+dx[i],y+dy[i],maze))
				q.push({x+dx[i],y+dy[i],step+1,i,1LL});
		}
	}
	if(ans!=1e17)
		cout<<ans<<endl;
	else
		cout<<-1<<endl;
}
// AC https://codeforces.com/contest/2041/submission/293790427

心路历程（WA，TLE，MLE……）

前面少include 一个cstring库，唉，都是clang不支持<bits/stdc.h>导致的