题解：CF2041D Drunken Maze

ccjjxx · 2024-11-26 17:24:23 · 题解

图论题，考完发现都写的是 dijkstra，但是我写的是 BFS。

首先先正常写，然后对于每个状态记录现在的方向和朝这个方向连续走了多少次，显然，当次数等于 4 时，你需要换方向，如果要沿同一防线继续走，就需要后退一步再前进两步。

这时就有 hack 来卡我了，如果按照这种方式连续朝同一方向前进，那么这样后退再前进的花费会是 2，也就是消耗了一次向前走的机会。但是，如果现在的左右（或上下）有空格子，你可以向别的方向换一下，再朝原方向前进，这样花费是 1。举个例子：

S.........T
...........

这样的路，你可以直接直线行走，也可以向前走两格再向下移动，再回来，是更优的。

有个细节，就是优先队列中有位置相同，答案相同，但是方向来源不同的点，为了保证正确性，你需要把符合这些条件的所有点全部跑出来，而不是只取第一个，有这样一个 hack 数据，找到了我在赛时的错误（来自 @Baiyj）。

5 18
S................T
.################.
.################.
..##....##....##..
..................

附上有很多 hack 数据的代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int stx,sty,edx,edy;
struct node{
    int x,y;
    int val,f;
    int pre,prepos;
    inline bool operator<(const node &ll) const
    {
        if(x==ll.x&&pre==ll.pre&&val==ll.val) return y>ll.y;
        if(pre==ll.pre&&val==ll.val) return x>ll.x;
        if(val==ll.val) return pre>ll.pre;
        return val>ll.val;
    }
};
priority_queue<node>q;
int dx[5]={0,0,1,-1,0};
int dy[5]={0,1,0,0,-1};
inline int man(int a,int b,int x,int y)
{
    return abs(a-b)+abs(x-y);
}
signed main()
{
    cin>>n>>m;
    vector<vector<bool>> vis(n+5,vector<bool>(m+5,0)),mp(n+5,vector<bool>(m+5,0));
    for(int i=1;i<=n;i++)
    {
        string c;cin>>c;
        for(int j=0;j<m;j++) 
        {
            mp[i][j+1]=0,vis[i][j+1]=0;
            if(c[j]=='#') mp[i][j+1]=1;
            if(c[j]=='S') stx=i,sty=j+1;
            if(c[j]=='T') edx=i,edy=j+1;
        }
    }
    q.push({stx,sty,0,man(stx,sty,edx,edy),0,0});
    int ans=1e9;
    while(!q.empty())
    {
        node now=q.top();q.pop();

        if(now.x==edx&&now.y==edy)
        {
            ans=min(ans,now.val);
            break;
        }
        if(vis[now.x][now.y]) continue;
        vis[now.x][now.y]=1;
        bool tt=0;
        do
        {
            if(tt) now=q.top(),q.pop();
            tt=1;
            for(int i=1;i<=4;i++)
            {
                node nxt=now;
                nxt.x+=dx[i],nxt.y+=dy[i];
                if(nxt.x<1||nxt.y<1||nxt.x>n||nxt.y>m||mp[nxt.x][nxt.y]) continue;
                if(i==nxt.prepos) nxt.pre++;
                else nxt.pre=0;
                nxt.val++;
                if(nxt.pre==3) 
                {
                    if(i==2||i==3)
                    {
                        node nxx=now;
                        nxx.x+=dx[1],nxx.y+=dy[1];
                        if(!(nxx.x<1||nxx.y<1||nxx.x>n||nxx.y>m||mp[nxx.x][nxx.y]))
                        {
                            nxt.pre=0,nxt.val+=2;
                        }
                        else
                        {
                            nxx=now;
                            nxx.x+=dx[4],nxx.y+=dy[4];
                            if(!(nxx.x<1||nxx.y<1||nxx.x>n||nxx.y>m||mp[nxx.x][nxx.y]))
                                nxt.pre=0,nxt.val+=2;
                            else nxt.val+=2,nxt.pre=1;
                        }
                    }
                    else
                    {
                        node nxx=now;
                        nxx.x+=dx[2],nxx.y+=dy[2];
                        if(!(nxx.x<1||nxx.y<1||nxx.x>n||nxx.y>m||mp[nxx.x][nxx.y]))
                        {
                            nxt.pre=0,nxt.val+=2;
                        }
                        else
                        {
                            nxx=now;
                            nxx.x+=dx[3],nxx.y+=dy[3];
                            if(!(nxx.x<1||nxx.y<1||nxx.x>n||nxx.y>m||mp[nxx.x][nxx.y]))
                                nxt.pre=0,nxt.val+=2;
                            else nxt.val+=2,nxt.pre=1;
                        }
                    }
                }
                else nxt.prepos=i;
                nxt.f=nxt.val+man(nxt.x,nxt.y,edx,edy);
                q.push(nxt);
            }
        }while(q.top().x==now.x&&q.top().y==now.y&&q.top().val==now.val&&q.top().prepos!=now.prepos);
    }
    if(ans==1e9)
    cout<<"-1";
    else cout<<ans;
}
/*
6 5
.S#..
#.#..
.....
#.#..
.....
.#..T

2 12
S..........T
.##..#..##..

2 7
S.....T
....##.

#..#..
S.....
##..#

5 8
S....#T.
#...#.#.
#.#.....
#...##..
##......

7 12
############
#S.........#
#####.######
#T..#.######
#...#.######
#.....######
############

5 7
S....#T
.#.#.#.
.#.#.#.
.#.#.#.
.......

2 10
S........T
##.####..#

5 18
S................T
.################.
.################.
..##....##....##..
..................

*/