题解 SP22393 【KATHTHI - KATHTHI】

SP22393 KATHTHI - KATHTHI

CSP J/S 2021 初赛考完了，发篇题解记录下自己的退役（

rp++!

我的双端队列广搜学习笔记

双端队列广搜，又称 01BFS ，是一类用来解决图上只有 01 边权的利器。

复习的时候做到这题，换了一种自认为更好的写法。

要广搜显然要满足两段性，这时如果按一般的写法都从队尾入队就无法满足条件了。

但是注意到只有两种边权，于是我们可以使用双端队列，总代价改变时从队尾入队，否则从队头入队，每次从队头取出元素扩展，这样可以保证短的先遍历到。

Talk is cheap, show me the code.

inline int bfs()
{
    deque < pair<int,int> > q;
    for(int i=1;i<=n;i++)   
        for(int j=1;j<=m;j++) dis[i][j]=1e9;
    dis[1][1]=0;
    q.push_back({1,1});
    int x,y;
    while(!q.empty())
    {
        x=q.front().first; y=q.front().second;
        if(x == n && y == m) return dis[x][y];
        q.pop_front();
        for(int i=0,nx,ny;i<4;i++)
        {
            nx=nxt[i][0]+x; ny=nxt[i][1]+y;
            if(nx < 1 || ny < 1 || nx > n || ny > m) continue ;
            if(dis[nx][ny] > dis[x][y]+(map[x][y] != map[nx][ny]))
            {
                dis[nx][ny]=dis[x][y]+(map[x][y] != map[nx][ny]);
                if(map[x][y] == map[nx][ny]) q.push_front({nx,ny});
                else q.push_back({nx,ny});
            }
        }
    }
    return dis[n][m];
}

Thank you for your reading !