拖拉机_牛客博客

思路

首先，读题把原问题抽象为模型（矩阵），然后思考如何转化为具体的算法，可以发现，这个问题可以转化为最短路模型，

点是所有的格子，边是上下左右四个方向。有障碍物时，点权为1，空地点权则为0。移除干草捆的最小数量就是起点到原点（0，0）的最短距离。

经过上述分析，我们就把原题转化为了最短路模型，我们可以使用Dijkstra算法求解，但是注意到一个性质：

在这个图中，点权只能取1或者0

具有这种性质的最短路可以使用双端队列BFS求解，能够在线性时间内完成求解。

因为只存在0和1，我们可以把Dijkstra算法中的堆简化成双端队列，从而省去了 $O (l o g n)$ 的时间，变得更加高效。至于双端队列BFS虽然名字看起来和BFS有点相似，但是它其实和BFS没啥关系，它的逻辑其实是和Dijkstra算法是一模一样的。

双端队列广搜的步骤是：

维护一个双端队列
每次从队头获取节点，进行松弛操作
- 如果碰到权重为1的边，则把更新后的节点加入队尾
- 如果碰到权重为0的边，则把更新后的节点加入队头
从而能够保证每次从队头获取的节点都是距离源点最小的顶点，这个性质是可以证明的。

alt

还有一个要注意的问题，双端队列BFS和普通BFS代码实现里面都有一个st数组，但是这两个数组是完全不同的东西。

双端里面是用来记录队列里面冗余元素的，st[t]=true代表顶点t的最短距离已经确定了，deque里面的t是冗余的。在出队后判断

BFS里面是用来记录是否已经被搜索到，st[t]=true代表该点在之前已经被搜索过了，最短距离已经确定了，不需要搜索了。在入队时判断

代码

//双端队列BFS
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 1010;

int n;
int g[N][N];
int dist[N][N];
int st[N][N];

int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};

int dijkstra(int sx, int sy)
{
    memset(dist, 0x3f, sizeof dist);
    dist[sx][sy] = 0;
    
    deque<PII> q;//front全是0，back全是1
    q.push_front({sx,sy});
    
    while(q.size())
    {
        auto t = q.front();q.pop_front();
        
        if(st[t.first][t.second]) continue;
        st[t.first][t.second] = true;
        
        for(int i = 0; i < 4; i++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];
            
            if(a < 0 || a > N || b < 0 || b > N) continue;
            
            if(dist[a][b] > dist[t.first][t.second] + g[a][b])
            {
                dist[a][b] = dist[t.first][t.second] + g[a][b];
                if(g[a][b] == 1) q.push_back({a, b});
                else q.push_front({a, b});
            }
        }
    }
    return dist[0][0];
}

int main()
{
    int sx, sy;
    cin >> n >> sx >> sy;
        
    for(int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }
    
    cout << dijkstra(sx, sy) << endl;
    
    return 0;
}

//超时的堆优化版的Dijkstra
//Dijkstra
#include<bits/stdc++.h>

using namespace std;

struct Edge
{
    int w, x, y;
    
    bool operator<(const Edge &t)const
    {
        return w > t.w;
    }
};
const int N = 1010;

int n, sx, sy;
int g[N][N];
int dist[N][N];
bool st[N][N];

int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[sx][sy] = 0;

    priority_queue<Edge> heap;  
    heap.push({0, sx, sy});

    while(heap.size())
    {
        auto t = heap.top();heap.pop();

        if(st[t.x][t.y]) continue;
        st[t.x][t.y] = true;

        //扩展
        for(int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a < 0 || a > N || b < 0 || b > N) continue;
            if(dist[a][b] > dist[t.x][t.y] + g[a][b])
            {
                dist[a][b] = dist[t.x][t.y] + g[a][b];
                heap.push({dist[a][b], a, b});
            }
        }
    }
    
    return dist[0][0];
}

int main()
{
    cin >> n >> sx >> sy;
    for(int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }

    int t = dijkstra();

    cout << t << endl;

    return 0;
}