D. Drunken Maze（醉迷宫） · znzryb
## 思路讲解
这题难点主要就是不要怕，看起来好像很难，但其实就只有16种状态，我还没加快读只跑了171ms。
看了一下大佬的思路，主要就是状态分解，还是分层图的思想。
```cpp
// 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代码
注意，该写法仅能在C++11及以上环境中编译（C++98好像没有array）
[https://codeforces.com/contest/2041/submission/293790427](https://codeforces.com/contest/2041/submission/293790427)
```cpp
#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>导致的