博客

原题链接：

2019. 拖拉机 – AcWing题库高质量的算法题库https://www.acwing.com/problem/content/2021/

思路：

双端队列bfs，本题存在权重为0的边，即没有干草堆的路径，由于本题求的是最少移除干草堆的数量，所以有干草堆的路径可能对答案有贡献，即边权为1，这种情况显然直接bfs解决不了，因为普通bfs只能处理边权都一样且大于等于0的图，所以本题采用双端队列，每次入队的时候判断一下，把边权为0的边入队头，边权为1的边入队尾，直观上来讲就是先处理非干草堆的连通块，再处理干草堆连通块，由于bfs遍历的路径一定是最小，所以能保证干草堆和非干草堆的连通块相交最少，即移除的干草堆最少

Code：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
deque<PII> q;
char g[N][N];
bool st[N][N];
int dist[N][N];
int w[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs(int x,int y)
{
    q.push_back({x,y});
    st[x][y]=true;
    dist[x][y]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop_front();
        for(int i=0;i<4;i++)
        {
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a<0||b<0||a>N-5||b>N-5||st[a][b]) continue;
            st[a][b]=true;
            if(w[a][b]) q.push_back({a,b});
            else
            q.push_front({a,b});

            dist[a][b]=dist[t.first][t.second]+w[t.first][t.second];
        }
    }

}
int main()
{
    int n,x,y;
    cin>>n>>x>>y;
    memset(g,'.',sizeof g);

    g[x][y]='&';
    while (n -- )
    {
        int x,y;
        cin>>x>>y;
        g[x][y]='#';
        w[x][y]=1;
    }

    bfs(x,y);

    cout<<dist[0][0];
    return 0;
}

作者：机械之忍
链接：https://www.acwing.com/activity/content/code/content/2246447/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。