leetcode-1631

Today’s leetcode daily question is a medium difficulty question, but the various ideas of the solution are really innovative, and I will record it here.

Every time I encounter such imaginative solutions, I feel very happy. They just use some methods that you have already mastered, but they can be used very skillfully.

Topic

https://leetcode-cn.com/problems/path-with-minimum-effort/

You are about to take part in a hike. You are given a map heights of two-dimensional rows x columns, where heights [row] [col] represents the height of the grid (row, col). At first you are in the upper left corner of the grid (0,0), and you want to go to the lower right corner of the grid (rows-1, columns-1) (note that the subscripts are numbered from 0). You can move up, down, left, right, one of the four directions at a time, and you want to find a path that is least expensive, physically, and physically.

The Health Point cost of a path is determined by the maximum absolute value of the height difference between adjacent cells on the path.

Please return the minimum physical exertion value from the upper left corner to the lower right corner.

Problem solution

Method 1: Backtracking

The first method is the one I first thought of, using the idea of backtracking to enumerate all the possibilities, and then choose the smallest.

This method is feasible, but it will timeout, which is not the focus of my record this time, so I will not put the code.

Method 2: Dichotomy + BFS

We can transform this problem into a “decision” problem, namely:

Is there a path from the upper left corner to the lower right corner that does not exceed the maximum of all edge weights

This determination problem is not complicated to solve, we just start from the upper left corner of the depth-first search or breadth-first search, in the search process is only allowed to pass through the edge weight of not more than xx, after the search to determine whether it can reach the lower right corner.

var minimumEffortPath = function(heights) {
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];

    const m = heights.length, n = heights[0].length;
    let left = 0, right = 999999, ans = 0;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const queue = [[0, 0]];
        const seen = new Array(m * n).fill(0);
        seen[0] = 1;
        while (queue.length) {
            const [x, y] = queue.shift();
            for (let i = 0; i < 4; i++) {
                const nx = x + dirs[i][0];
                const ny = y + dirs[i][1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !seen[nx * n + ny] && Math.abs(heights[x][y] - heights[nx][ny]) <= mid) {
                    queue.push([nx, ny]);
                    seen[nx * n + ny] = 1;
                }
            }
        }
        if (seen[m * n - 1]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
};

The core idea of this code:

• Constantly obtain mid values through dichotomy
• Breadth-first traversal of the graph starting from (0,0), but unlike normal BFS, if the weight between parent and child exceeds mid, then the relationship between parent and child is considered to be severed
• According to the traversal result of the previous step, see if we can traverse the node in the lower right corner. If so, it means that when our physical exertion is mid, there is a way for us to go to the lower right corner, then continue to split

And collect

And the introduction of the collection can be seen here: https://sunra.top/posts/c2448c65/

We put these mn nodes into the collection and maintain their connectivity in real time.

Since we need to find the shortest path from the upper left corner to the lower right corner, we can order all edges in the graph from the smallest to the largest weight, and add them in turn and search the set. When we add an edge with weight xx, if the upper left and lower right corners change from non-connected to connected, then xx is the answer.

var minimumEffortPath = function(heights) {
    const m = heights.length;
    const n = heights[0].length;
    const edges = [];
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            const id = i * n + j;
            if (i > 0) {
                edges.push([id - n, id, Math.abs(heights[i][j] - heights[i - 1][j])]);
            }
            if (j > 0) {
                edges.push([id - 1, id, Math.abs(heights[i][j] - heights[i][j - 1])]);
            }
        }
    }
    edges.sort((a, b) => a[2] - b[2]);

    const uf = new UnionFind(m * n);
    let ans = 0;
    for (const edge of edges) {
        const x = edge[0], y = edge[1], v = edge[2];
        uf.unite (x, y);
        if (uf.connected(0, m * n - 1)) {
            ans = v;
            break;
        }
    }
    return ans;
};

//and look up templates
class UnionFind {
    constructor (n) {
        this.parent = new Array(n).fill(0).map((element, index) => index);
        this.size = new Array(n).fill(1);
        //Current number of connected components
        this.setCount = n;
    }

    findset (x) {
        if (this.parent[x] = x) {
            return x;
        }
        this.parent[x] = this.findset(this.parent[x]);
        return this.parent[x];
    }

    unite (a, b) {
        let x = this.findset(a), y = this.findset(b);
        if (x = y) {
            return false;
        }
        if (this.size[x] < this.size[y]) {
            [x, y] = [y, x];
        }
        this.parent[y] = x;
        this.size[x] += this.size[y];
        this.setCount -= 1;
        return true;
    }

    connected (a, b) {
        const x = this.findset(a), y = this.findset(b);
        return x = y;
    }
}