• Sources：D-Drunken Maze
• Abstract：給定 $n\times m(12\le n\times m\le 2\times 10^5,3\le n,m\le 10^4)$的地圖，# 表示墻壁，. 表示空地，S 表示起點，T 表示終點。要求不能超過連續$3$步走同一方向，不可以通過障礙。起點終點視作空地。問 S 到 T 的最小步數。若無解輸出 $?1$。
• Keyword：搜索(銅牌題)
• Solution：注意到$n$和$m$非常大，因此無法用結構體存圖。改用動態處理隊列。設計狀態數組$dist$，注意到圖中每個點可通過求解其$id$進而將狀態數組壓至三維。$dist[id][dir][cnt]$代表沿$dir$方向上經過$cnt$次到達頂點$id$。注意處理當$cnt$到達$3$時不可繼續沿此方向繼續走。
• Code：實現上可采用$BFS$，或$DFS$+記憶化。下面給出$BFS$實現。

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e4;
const int INF=1e9;
char mapp[MAX][MAX];
int n,m,sy,sx,ty,tx;
struct node{
    int y,x,pre_dir,cnt;//pre_dir:上一步自何方向而來,0-4 cnt:方向上已經走了多少步,0-2
};
queue<node>q;
int getid(int y,int x){//計算頂點坐標
    return y*m+x;
}
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//(y,x):right,left,down,up
bool check1(int y,int x){//越界/撞墻檢測
    return y>=0&&y<n&&x>=0&&x<m&&mapp[y][x]!='#';
}
bool check2(int y,int x){//終點檢測
    return x==tx&&y==ty;
}
void bfs(){
    vector<vector<vector<int>>>dis(n*m,vector<vector<int>>(4,vector<int>(3,INF)));//狀態數組,三個維度分別表示id,dir,cnt,初始化所有點均為不可達
    for(int i=0;i<4;i++){//處理起點的四個方向
        int ny=sy+dir[i][0],nx=sx+dir[i][1];
        if(check1(ny,nx)){//越界/撞墻檢測
            int id=getid(ny,nx);
            if(dis[id][i][0]>1){//起點擴散的點一定可達
                dis[id][i][0]=1;
                q.push({ny,nx,i,1});
            }
        }
    }
    bool f=0;//判斷是否有解
    while(q.size()){
        int ans=dis[getid(q.front().y,q.front().x)][q.front().pre_dir][q.front().cnt-1];
        if(check2(q.front().y,q.front().x)){//已到達終點
            cout<<ans,f=1;
            break;
        }
        for(int i=0;i<4;i++){//考察當前點的四個方向
            int now=0;//記錄當前方向上走的步數
            if(i==q.front().pre_dir){//沿當前方向繼續走
                now=q.front().cnt+1;
                if(now>3) continue;//不能繼續走了
            }else now=1;//未沿當前方向繼續走
            int ny=q.front().y+dir[i][0],nx=q.front().x+dir[i][1];
            if(check1(ny,nx)){//越界/撞墻檢測
                if(dis[getid(ny,nx)][i][now-1]>ans+1){//可以擴散的點一定可達
                    dis[getid(ny,nx)][i][now-1]=ans+1;
                    q.push({ny,nx,i,now});
                }
            }
        }
        q.pop();
    }
    if(!f) cout<<-1;//無解
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            cin>>mapp[i][j];
            //記錄特殊點S和T的位置
            if(mapp[i][j]=='S') sy=i,sx=j;
            else if(mapp[i][j]=='T') ty=i,tx=j;
        }
    bfs();
    return 0;
}