Задача: 675. Cut Off Trees for Golf Event
Сложность: hard

Есть лес в виде матрицы. В каждой ячейке:
0 — непроходимо
1 — проходимо
>1 — дерево (высота = значение)
Нужно срубить все деревья в порядке возрастания высоты, начиная с (0, 0), минимизируя количество шагов. Если добраться до какого-то дерева невозможно — вернуть -1.

Пример:

Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.

👨‍💻 Алгоритм:

1⃣Начиная с (0, 0), для каждого дерева в порядке возрастания высоты будем вычислять расстояние от текущего местоположения до следующего дерева (и перемещаться туда), добавляя это расстояние к ответу.

2⃣Формулируем задачу как предоставление функции расстояния dist(forest, sr, sc, tr, tc), которая вычисляет расстояние от точки (sr, sc) до цели (tr, tc) с учетом препятствий, где dist[i][j] == 0. (Эта функция расстояния вернет -1, если путь невозможен.)

3⃣Далее следует код и анализ сложности, которые общие для всех трех подходов. Затем алгоритмы, представленные в наших подходах, будут сосредоточены только на предоставлении нашей функции dist.

😎 Решение:

function cutOffTree($forest) {
    $trees = [];
    $rows = count($forest);
    $cols = count($forest[0]);

    for ($r = 0; $r < $rows; $r++) {
        for ($c = 0; $c < $cols; $c++) {
            if ($forest[$r][$c] > 1) {
                $trees[] = [$forest[$r][$c], $r, $c];
            }
        }
    }

    usort($trees, function($a, $b) {
        return $a[0] - $b[0];
    });

    $sr = 0;
    $sc = 0;
    $ans = 0;

    foreach ($trees as $tree) {
        [$value, $tr, $tc] = $tree;
        $d = dist($forest, $sr, $sc, $tr, $tc);
        if ($d < 0) {
            return -1;
        }
        $ans += $d;
        $sr = $tr;
        $sc = $tc;
    }

    return $ans;
}

function dist($forest, $sr, $sc, $tr, $tc) {
    
    return 0;
}

Ставь 👍 и забирай 📚 Базу знаний