二维数组中修改代价最小问题【转换题意+最短路径】(Dijkstra+01BFS)

• 题目规律：在二维数组上给定起始点和终止点，且二维数组中有一些限定走法的障碍，可以将障碍消除/修改，需要我们找到从起始点到终止点的最小的修改次数。
• 考虑每个点都是一个节点，在任意位置都可以任意移动，但是不能走出边界，如果移动符合要求，则移动的代价为0，否则移动的代价为1。
• 这样就可以把二维数组转换为一个包含mn个点的图，每个节点都和最多相邻的4个节点相连，边的权值要么为0，要么为1（符合移动要求）。
• 在图G上运用任意的最短路算法，求解出从起始点到终止点的最短路。关于Dijkstra的朴素算法和小根堆优化可以见我的另一篇博客单源最短路径算法【朴素Dijkstra+小根堆优化】

• 到达角落需要移除障碍物的最小数目
• 使网格图至少有一条有效路径的最小代价
• 0-1BFS

原题在题目

• 我们需要从(0,0)到达(m-1,n-1)，经过一个障碍物的代价为1，经过空单元格的代价为0，转换为从起始点到终止点的最短路，采用Dijkstra优先队列进行优化，代码如下：

vector>dir={{-1,0},{0,-1},{1,0},{0,1}};
int minimumObstacles(vector>& grid) {
    int m=grid.size();
    int n=grid[0].size();
    priority_queue,vector>,greater<>>q;
    q.emplace(0,0);
    vectordist(n*m,INT_MAX/2);
    while(!q.empty()){
        auto p=q.top();
        q.pop();
        int spot=p.second;
        int dis=p.first;
        if(dist[spot]
            int dx=x+d[0];
            int dy=y+d[1];
            int new_spot=dx*n+dy;
            int new_dis=dis+(grid[x][y]==1); //经过一个障碍物到达(dx,dy)，路径+1
            if(dx>=0&&dy>=0&&dx //通过(x,y)可以松弛(0,0)到达(dx,dy)的路径长
                dist[new_spot]=new_dis; //松弛操作
                q.emplace(new_dis,new_spot);
            }
        }
    }
    return dist[m*n-1]; //返回到达终点的最短距离
}

原题在使网格图至少有一条有效路径的最小代价

• 按照要求，在任一点可以向任意一个位置移动，但不能走出边界，如果移动方向与(i,j)处的箭头方向一致，那么移动代价为0，否则移动代价为1。
• 题目要求每个格子中的数字只能修改一次，事实上，我们发现一定存在一条路径，它只经过每个位置最多一次。使用Dijkstra优先队列优化

vector>dir={{0,1},{0,-1},{1,0},{-1,0}};
int minCost(vector>& grid) {
    int m=grid.size();
    int n=grid[0].size();
    vectordist(m*n,INT_MAX/2);
    dist[0]=0;
    priority_queue,vector>,greater<>>q;
    q.push(make_pair(0,0));
    while(!q.empty()){
        auto p=q.top();
        q.pop();
        int weight=p.first;
        int spot=p.second;
        if(dist[spot]
            int dx=x+dir[i][0];
            int dy=y+dir[i][1];
            int new_spot=dx*n+dy;
            int len=(i+1==grid[x][y]?0:1);
            int new_weight=weight+len;
            if(dx>=0&&dy>=0&&dx
                dist[new_spot]=new_weight;
                q.emplace(new_weight,new_spot);
            }
        }
    }
    return dist[m*n-1];
}

• 考虑边权为0和1的图，当位于任意顶点u时，其边权为0和1，与Dijkstra类似，我们只有在前一个顶点松弛时才会将一个顶点放入队列中(通过在此边上来减小距离)，并且我们还在每个时间点按照与源点的距离入队列进行排序。
• 当我们处在点u时，通过一条边（u,v）可知，点v要么和u处在同一水平，要么处在比u大1的水平。在BFS期间，我们的队列最多保存两个连续的水平的顶点，及L(u)和L(u)+1，因此在采用BFS时，如果顶点v是松弛的并且具有和u相同的水平，我们将其推到队列的最前面，如果他具有下一个水平，我们将其推到队列的末尾，及保持BFS的层序的特点。
• 正常的队列的数据结构不能在O(1)中插入并保持顺序，使用优先队列需要O(logN)来保持排序，因此我们可以采用双端队列进行操作，他具有：删除顶部元素(获取DFS的顶点)、在开头插入(推送具有相同水平的顶点)、在末尾插入(将顶点推到下一水平)。

使网格图至少有一条有效路径的最小代价的代码如下：

vector>dir={{0,1},{0,-1},{1,0},{-1,0}};
int minCost(vector>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector dist(m * n, INT_MAX/2);
    vector vis(m * n, 0);
    dist[0] = 0;
    deque q;
    q.push_back(0);
    
    while (!q.empty()) {
        auto cur_pos = q.front();
        q.pop_front();
        if (vis[cur_pos]) {
            continue;
        }
        vis[cur_pos] = 1;
        int x = cur_pos / n;
        int y = cur_pos % n;
        for (int i = 0; i < 4; ++i) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            int new_pos = dx * n + dy;
            int new_dis = dist[cur_pos] + (grid[x][y] != i + 1);
            
            if (dx >= 0 && dx < m && dy >= 0 && dy < n && new_dis < dist[new_pos]) {
                dist[new_pos] = new_dis;
                if (grid[x][y] == i + 1) {
                    q.push_front(new_pos);
                }
                else {
                    q.push_back(new_pos);
                }
            }
        }
    }

    return dist[m * n - 1];
}

对比Dijkstra，双端队列带来了更简单的时间复杂度。