675. Cut Off Trees for Golf Event
leetcode hard
Task
Вам необходимо срубить все деревья в лесу для проведения гольф-мероприятия. Лес представлен в виде матрицы m x n. В этой матрице:
- 0 означает, что ячейка непроходима.
- 1 представляет собой пустую проходимую ячейку.
- Число больше 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.
C# solution
matched/originalpublic class Solution {
public int CutOffTree(IList<IList<int>> forest) {
var trees = new List<(int height, int r, int c)>();
for (int r = 0; r < forest.Count; ++r) {
for (int c = 0; c < forest[r].Count; ++c) {
if (forest[r][c] > 1) {
trees.Add((forest[r][c], r, c));
}
}
}
trees.Sort((a, b) => a.height.CompareTo(b.height));
int sr = 0, sc = 0, ans = 0;
foreach (var tree in trees) {
int tr = tree.r, tc = tree.c;
int d = Dist(forest, sr, sc, tr, tc);
if (d < 0) return -1;
ans += d;
sr = tr;
sc = tc;
}
return ans;
}
private int Dist(IList<IList<int>> forest, int sr, int sc, int tr, int tc) {
// Implement the distance function here
return 0;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int CutOffTree(IList<vector<int>> forest) {
var trees = new List<(int height, int r, int c)>();
for (int r = 0; r < forest.size(); ++r) {
for (int c = 0; c < forest[r].size(); ++c) {
if (forest[r][c] > 1) {
trees.push_back((forest[r][c], r, c));
}
}
}
trees.Sort((a, b) => a.height.CompareTo(b.height));
int sr = 0, sc = 0, ans = 0;
foreach (var tree in trees) {
int tr = tree.r, tc = tree.c;
int d = Dist(forest, sr, sc, tr, tc);
if (d < 0) return -1;
ans += d;
sr = tr;
sc = tc;
}
return ans;
}
private int Dist(IList<vector<int>> forest, int sr, int sc, int tr, int tc) {
// Implement the distance function here
return 0;
}
}Java solution
matched/originalclass Solution {
public int cutOffTree(List<List<Integer>> forest) {
List<int[]> trees = new ArrayList<>();
for (int r = 0; r < forest.size(); r++) {
for (int c = 0; c < forest.get(r).size(); c++) {
if (forest.get(r).get(c) > 1) {
trees.add(new int[]{forest.get(r).get(c), r, c});
}
}
}
trees.sort(Comparator.comparingInt(a -> a[0]));
int sr = 0, sc = 0, ans = 0;
for (int[] tree : trees) {
int tr = tree[1], tc = tree[2];
int d = dist(forest, sr, sc, tr, tc);
if (d < 0) return -1;
ans += d;
sr = tr;
sc = tc;
}
return ans;
}
private int dist(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {
// Implement the distance function here
return 0;
}
}JavaScript solution
matched/originalvar cutOffTree = function(forest) {
const trees = [];
for (let r = 0; r < forest.length; r++) {
for (let c = 0; c < forest[0].length; c++) {
if (forest[r][c] > 1) {
trees.push([forest[r][c], r, c]);
}
}
}
trees.sort((a, b) => a[0] - b[0]);
let sr = 0, sc = 0, ans = 0;
for (const [_, tr, tc] of trees) {
const 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) {
// Implement the distance function here
return 0;
}Python solution
matched/originalclass Solution(object):
def cutOffTree(self, forest):
trees = sorted((v, r, c) for r, row in enumerate(forest)
for c, v in enumerate(row) if v > 1)
sr = sc = ans = 0
for _, tr, tc in trees:
d = self.dist(forest, sr, sc, tr, tc)
if d < 0:
return -1
ans += d
sr, sc = tr, tc
return ans
def dist(self, forest, sr, sc, tr, tc):
# Implement the distance function here
return 0Go solution
matched/originalfunc cutOffTree(forest [][]int) int {
type Tree struct {
height, r, c int
}
var trees []Tree
for r, row := range forest {
for c, v := range row {
if v > 1 {
trees = append(trees, Tree{v, r, c})
}
}
}
sort.Slice(trees, func(i, j int) bool {
return trees[i].height < trees[j].height
})
sr, sc, ans := 0, 0, 0
for _, tree := range trees {
tr, tc := tree.r, tree.c
d := dist(forest, sr, sc, tr, tc)
if d < 0 {
return -1
}
ans += d
sr, sc = tr, tc
}
return ans
}
func dist(forest [][]int, sr, sc, tr, tc int) int {
// Implement the distance function here
return 0
}Explanation
Algorithm
Начиная с (0, 0), для каждого дерева в порядке возрастания высоты будем вычислять расстояние от текущего местоположения до следующего дерева (и перемещаться туда), добавляя это расстояние к ответу.
Формулируем задачу как предоставление функции расстояния dist(forest, sr, sc, tr, tc), которая вычисляет расстояние от точки (sr, sc) до цели (tr, tc) с учетом препятствий, где dist[i][j] == 0. (Эта функция расстояния вернет -1, если путь невозможен.)
Далее следует код и анализ сложности, которые общие для всех трех подходов. Затем алгоритмы, представленные в наших подходах, будут сосредоточены только на предоставлении нашей функции dist.
😎