题解：CF2041D Drunken Maze

· · 题解

思路

广搜~~
记录每一步朝哪个方向连续走了几步，根据题意，如果上一步连续走同一个方向的步数等于 3，这一步就不能走这个方向。
然后写代码的时候注意判断边界和墙，注意换方向进队时连续步数要归一就好啦！
但是：TLE。
小优化：
记录是否有朝某个方向连续走了某步走到一个节点，如果以前走到过（以前走到肯定比现在走到更优），那就不进队。
于是：AC 啦！
具体细节看代码吧！

代码

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int x,y,bw,sum,ans;
    //bw：上一步方向，sum：连续步数，ans：步数 
};
char a[10005][10005];
queue<Node>q;
int n,m,xx,yy,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>a[i][j]; 
            if(a[i][j]=='S')q.push({i,j,4,0,0});
            //找到起点，进队
            if(a[i][j]=='T'){xx=i;yy=j;}
            //找到终点，记录 
        }
    }
    int dis[4][3][n+5][m+5];
    //记录是否有朝某个方向连续走了某步走到一个节点的数组 
    memset(dis,0,sizeof(dis));
    while(q.size()){
        Node t=q.front();
        q.pop();
        int x=t.x,y=t.y,bw=t.bw,sum=t.sum,ans=t.ans;
        for(int i=0;i<4;++i){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<1||ny<1||nx>n||ny>m)continue;
            //判断是否超界 
            if(a[nx][ny]=='#'||bw==i&&sum==3)continue;
            //判断是否遇到墙或连续步数超限 
            if(bw==i&&dis[i][sum][nx][ny])continue;
            if(bw!=i&&dis[i][0][nx][ny])continue;
            //如果以前以同样的方式走到同样的格，舍弃 
            dis[i][(bw==i?sum:0)][nx][ny]=1;
            //记录 
            if(nx==xx&&ny==yy){
                cout<<ans+1<<"\n";
                return 0;
            }
            //如果到达，输出答案 
            if(bw==i)q.push({nx,ny,i,sum+1,ans+1});
            else q.push({nx,ny,i,1,ans+1});
            //入队，注意方向是否和上一步相同 
        }
    }
    cout<<-1<<"\n";
    //无发到达，输出-1 
    return 0;
}