AT213_E

· · 个人记录

典型的01BFS,也叫双端队列BFS。

在最基本的BFS中，每次向邻居状态扩展的时候记为“一步 ，我们通过逐层搜索，可以解决从起点到每个状态点的最少步数，这本质上等价于在一个边权为1的图上进行层次遍历，求出每个点距离起点的最短距离（即层数）。每个点（状态）第一次入队，步数即为所求。

经常我们会遇到一类砸墙问题，砸一次墙需要花费1的代价，询问到从起点到终点最少需要砸几次墙。如果抽象出来，就是状态与状态之间要么代价是0，要么代价是1，构成一幅边权是0或者1的图，询问到起点最短路，本质上面可以用最短路路算法求，但是针对这种特殊问题，有更容易的做法。

我们想一想，bfs先走到能走的地方，然后花代价1去砸周边的墙，可以用两个队列实现，进一步抽象，我们可以利用双端队列，完成这个过程。

如果这条分支边权是0的边，从队首进入，如果这个边权是1从队尾进入。循环从队首出队，按照上述过程访问所有邻居状态，直到队空。

队首维护不需要花代价的部分，队尾维护增加代价为1的部分。

时间复杂度：O(hw)

题目链接

#include<bits/stdc++.h>
using namespace std;
const int N=505;
string s[N];
int h,w;
struct node{
    int x,y,step;
};
int vis[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool check(int i,int j)
{
    if(i<0||i>=h||j<0||j>=w)return false;
    return true;
}
void bfs()
{
    memset(vis,-1,sizeof(vis));
    deque<node>que;       //双端队列 
    que.push_back((node){0,0,0});

    while(que.size())
    {
        node t=que.front(); que.pop_front();

        int x=t.x,y=t.y,step=t.step;
        if(vis[x][y]!=-1)continue;

        vis[x][y]=step;

        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(check(xx,yy)&&s[xx][yy]=='.')   //将代价为0的邻居状态，插入队首 
                que.push_front((node){xx,yy,step});
        }

        for(int i=-2;i<=2;i++)
            for(int j=-2;j<=2;j++)             //将代价为1的邻居状态，插入队尾 
            {
                if(abs(i)==2&&abs(j)==2)continue;   //如果只破环一次，不能走到（x+-2,y+-2）这个格子 
                int xx=x+i;
                int yy=y+j;
                if(check(xx,yy)&&s[xx][yy]=='#'&&vis[xx][yy]==-1)
                    que.push_back((node){xx,yy,step+1});
            }
    }
}

int main()
{
    cin>>h>>w;
    for(int i=0;i<h;i++)cin>>s[i];

    bfs();

    cout<<vis[h-1][w-1];

    return 0;
}

类似题目： ABC176D “Wizard in Maze”