ACwing寒假每日一题2022打卡 Day 4

原题链接：

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

思路：

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

Code：

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1010;
typedef pair PII;
deque 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< 
作者：机械之忍
 链接：https://www.acwing.com/activity/content/code/content/2246447/
 来源：AcWing
 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5702982.html