The problem of minimum modification cost in two-dimensional array [conversion question + shortest path] (dijkstra+01bfs)

• Topic regularity ： Give a start point and an end point on a two-dimensional array , And there are some obstacles in the two-dimensional array , Can remove obstacles / modify , We need to find the minimum number of modifications from the start point to the end point .
• Consider that each point is a node , You can move anywhere , But you can't go out of the border , If the movement meets the requirements , Then the cost of moving is 0, Otherwise the cost of moving is 1.
• In this way, you can convert a two-dimensional array into a containing mn A picture of a point , Each node is associated with the most adjacent nodes 4 Two nodes are connected , The weight of the edge is either 0, Either for 1（ Meet the movement requirements ）.
• In the figure G Using any shortest path algorithm , The shortest path from the starting point to the ending point is solved . About Dijkstra The naive algorithm and the small root heap optimization can be found in my other blog Single source shortest path algorithm 【 simple Dijkstra+ Small root heap optimization 】

The minimum number of obstacles that need to be removed to reach the corner

The original question is subject

• We need to go from (0,0) arrive (m-1,n-1), The cost of passing an obstacle is 1, The cost of passing through empty cells is 0, Convert to the shortest path from the starting point to the ending point , use Dijkstra Priority queue optimization , The code is as follows ：

vector<vector<int>>dir={
    {
    -1,0},{
    0,-1},{
    1,0},{
    0,1}};
int minimumObstacles(vector<vector<int>>& grid) {
    
    int m=grid.size();
    int n=grid[0].size();
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>q;
    q.emplace(0,0);
    vector<int>dist(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]<dis) continue; // It has been relaxed , skip 
        int x=spot/n;
        int y=spot%n;
        for(auto& d:dir){
    
            int dx=x+d[0];
            int dy=y+d[1];
            int new_spot=dx*n+dy;
            int new_dis=dis+(grid[x][y]==1); // Pass through an obstacle to reach (dx,dy), route +1
            if(dx>=0&&dy>=0&&dx<m&&dy<n&&new_dis<dist[new_spot]){
     // adopt (x,y) Can relax (0,0) arrive (dx,dy) Path length of 
                dist[new_spot]=new_dis; // Slack operation 
                q.emplace(new_dis,new_spot);
            }
        }
    }
    return dist[m*n-1]; // Return the shortest distance to the destination 
}

---

The minimum cost of making a grid graph have at least one effective path

The original question is The minimum cost of making a grid graph have at least one effective path

• In accordance with the requirements , You can move to any position at any point , But you can't go out of the border , If the moving direction is the same as (i,j) The direction of the arrow at is consistent , Then the cost of moving is 0, Otherwise, the moving cost is 1.
• The title requires that the number in each grid can only be modified once , in fact , We found that there must be a path , It only passes through each position at most once . Use Dijkstra Priority queue optimization

vector<vector<int>>dir={
    {
    0,1},{
    0,-1},{
    1,0},{
    -1,0}};
int minCost(vector<vector<int>>& grid) {
    
    int m=grid.size();
    int n=grid[0].size();
    vector<int>dist(m*n,INT_MAX/2);
    dist[0]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,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]<weight) continue;
        int x=spot/n;
        int y=spot%n;
        for(int i=0;i<4;i++){
    
            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<m&&dy<n&&new_weight<dist[new_spot]){
    
                dist[new_spot]=new_weight;
                q.emplace(new_weight,new_spot);
            }
        }
    }
    return dist[m*n-1];
}

---

0-1BFS

• Consider the edge weight as 0 and 1 Graph , When at any vertex u when , Its edge right is 0 and 1, And Dijkstra similar , We only put a vertex in the queue when the previous vertex is relaxed ( Reduce the distance by coming up here ), And at each time point, we rank according to the distance from the source point .
• When we are at point u when , Through a side （u,v） You know , spot v Either with u At the same level , Or it's better than u Big 1 The level of . stay BFS period , Our queue holds up to two consecutive horizontal vertices , And L(u) and L(u)+1, So... Is being used BFS when , If the vertex v Is loose and has and u The same level , We push it to the front of the queue , If he has the next level , We push it to the end of the queue , And keep BFS Characteristics of the sequence .
• The data structure of a normal queue cannot be in O(1) Insert and keep the order , Using priority queues requires O(logN) To keep the order , So we can use double ended queue to operate , He has ： Delete the top element ( obtain DFS The summit of )、 Insert... At the beginning ( Push vertices with the same level )、 Insert... At the end ( Push the vertex to the next level ).

The minimum cost code for making the grid graph have at least one effective path is as follows ：

vector<vector<int>>dir={
    {
    0,1},{
    0,-1},{
    1,0},{
    -1,0}};
int minCost(vector<vector<int>>& grid) {
    
    int m = grid.size();
    int n = grid[0].size();
    vector<int> dist(m * n, INT_MAX/2);
    vector<int> vis(m * n, 0);
    dist[0] = 0;
    deque<int> 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];
}

contrast Dijkstra, Double ended queues bring simpler time complexity .