And that’s how it works.

The title

I recently did a force puzzle,Leetcode-cn.com/problems/pa…

Train of thought

Leetcode-cn.com/problems/pa… Consult the big guy’s train of thought.

  • Abstract each vertex in the grid into a vertex in the graph.
  • Connect two adjacent cells with an edge whose length is the absolute value of the difference between the two cells
  • Find a shortest path from the top left to the bottom right, where the length of the path is defined as the maximum weight of all edges along the path

Method one and two

Divide the shortest path length by two. When we doubly enumerate to length x, we only keep all edges whose length is less than or equal to x. Then search from the top left corner, either BFS or DFS, and determine whether there is a path to the bottom right corner. If we get there, then we can decrease x, and if we don’t, we can increase it. The PHP code looks like this:

class Solution {

    /**
     * @param Integer[][] $heights
     * @return Integer
     */
    function minimumEffortPath($heights) {
        $row = count($heights);
        $col = count($heights[0]);
        $left = 0;
        $right = 999999;
        $res = 0;
        $directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
        while ($left < $right) {
            $mid = $left + (int)(($right - $left) / 2);
            $visited = array_fill(0, $row, array_fill(0, $col, 0));
            $queue = new SplQueue();
            $queue->enqueue([0, 0]);
            $visited[0][0] = 1;
            while (!$queue->isEmpty()) {
                $top = $queue->dequeue();
                $x = $top[0];
                $y = $top[1];
                foreach ($directions as $direction) {
                    $newX = $x + $direction[0];
                    $newY = $y + $direction[1];
                    if ($newX >= 0 && $newX < $row &&
                        $newY >= 0 && $newY < $col &&
                    $visited[$newX][$newY] == 0 &&
                        abs($heights[$newX][$newY] - $heights[$x][$y]) <= $mid
                    ) {
                        $queue->enqueue([$newX, $newY]);
                        $visited[$newX][$newY] = 1;
                    }
                }
            }
            if ($visited[$row - 1][$col - 1] == 1) {
                $right = $mid;
//                $res = $mid;
            } else {
                $left = $mid + 1;
            }
        }

        return $left;
    }

}
Copy the code

Method two, and look up the set

I didn’t realize this thing could work and be set up.

Add all edges in order of length and size to and look up the set, until the upper left corner and the lower right corner can be connected.

class Solution { /** * @param Integer[][] $heights * @return Integer */ function minimumEffortPath($heights) { $row = count($heights); $col = count($heights[0]); $edges = []; for ($i = 0; $i < $row; $i++) { for ($j = 0; $j < $col; $j++) { $id = $i * $col + $j; if ($i > 0) { $edges[] = [$id - $col, $id, abs($heights[$i][$j] - $heights[$i-1][$j])]; } if ($j > 0) { $edges[] = [$id - 1, $id, abs($heights[$i][$j] - $heights[$i][$j-1])]; }}} / / in accordance with the length of the edge ascending usort ($edges, function ($a, $b) {if ($a [2] > $b [2]) {return 1; } else { return -1; }}); $uf = new UnionFind($row * $col); foreach ($edges as $edge) { $uf->union($edge[0], $edge[1]); if ($uf->connection(0, $row * $col - 1)) { return $edge[2]; } } return 0; } function minimumEffortPathAC($heights) { $row = count($heights); $col = count($heights[0]); $left = 0; $right = 999999; $directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]; while ($left < $right) { $mid = $left + (int)(($right - $left) / 2); $visited = array_fill(0, $row, array_fill(0, $col, 0)); $queue = new SplQueue(); $queue->enqueue([0, 0]); $visited[0][0] = 1; while (! $queue->isEmpty()) { $top = $queue->dequeue(); $x = $top[0]; $y = $top[1]; foreach ($directions as $direction) { $newX = $x + $direction[0]; $newY = $y + $direction[1]; if ($newX >= 0 && $newX < $row && $newY >= 0 && $newY < $col && $visited[$newX][$newY] == 0 && abs($heights[$newX][$newY] - $heights[$x][$y]) <= $mid ) { $queue->enqueue([$newX, $newY]); $visited[$newX][$newY] = 1; } } } if ($visited[$row - 1][$col - 1] == 1) { $right = $mid; // $res = $mid; } else { $left = $mid + 1; } } return $left; } } class UnionFind { public $parents; public $count; public function __construct($n) { for ($i = 0; $i < $n; $i++) { $this->parents[$i] = $i; $this->count++; } } public function find($x) { while ($x ! = $this->parents[$x]) { $this->parents[$x] = $this->parents[$this->parents[$x]]; $x = $this->parents[$x]; } return $x; } public function union($x, $y) { $rootX = $this->find($x); $rootY = $this->find($y); if ($rootY == $rootX) { return; } $this->parents[$rootX] = $rootY; $this->count--; return; } public function connection($x, $y) { $rootX = $this->find($x); $rootY = $this->find($y); if ($rootY == $rootX) { return true; } return false; }}Copy the code