广度优先搜索：求解《675. 为高尔夫比赛砍树》

var cutOffTree = function(forest) {
  const m = forest.length, n = forest[0].length, forests = []
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) 
      if (forest[i][j] > 1) forests.push([i, j, forest[i][j]])
  forests.sort((a, b) => a[2] - b[2])
  const getDistance = ([sx, sy], [tx, ty]) => {
    const visited = Array.from({length: m}, _ => new Uint8Array(n))
    const drs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    const q = [[sx, sy]]
    let depth = -1
    while (q.length) {
      let l = q.length
      depth++
      while (l--) {
        const [x, y] = q.shift()
        if (x === tx && y === ty) return depth
        for (let i = 0; i < 4; i++) {
          const [dx, dy] = drs[i]
          const nx = x + dx, ny = y + dy
          if (nx < 0 || nx >= m || ny < 0 || ny >= n || forest[nx][ny] === 0 || visited[nx][ny] === 1) continue
          visited[nx][ny] = 1
          q.push([nx, ny])
        }
      }
    }
    return -1
  }
  let r = 0
  for (let i = 0; i < forests.length; i++) {
    const t = getDistance(forests[i - 1] || [0, 0], forests[i])
    if (t === -1) return -1
    r += t
  }
  return r
};

function cutOffTree(forest: number[][]): number {
  const m = forest.length, n = forest[0].length, forests = []
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) 
      if (forest[i][j] > 1) forests.push([i, j, forest[i][j]])
  forests.sort((a, b) => a[2] - b[2])
  const getDistance = ([sx, sy], [tx, ty]) => {
    const q = [[sx, sy]], drs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    const visited = Array.from({length: m}, _ => new Uint8Array(n))
    let depth = -1
    while (q.length) {
      let l = q.length
      depth++
      while (l--) {
        const [x, y] = q.shift()
        if (x === tx && y === ty) return depth
        for (let i = 0; i < 4; i++) {
          const [dx, dy] = drs[i]
          const nx = x + dx, ny = y + dy
          if (nx < 0 || nx >= m || ny < 0 || ny >= n || forest[nx][ny] === 0 || visited[nx][ny] === 1) continue
          visited[nx][ny] = 1
          q.push([nx, ny])
        }
      }
    }
    return -1
  }
  let r = 0
  for (let i = 0; i < forests.length; i++) {
    const t = getDistance(forests[i - 1] || [0, 0], forests[i])
    if (t === -1) return -1
    r += t
  }
  return r
};

func cutOffTree(forest [][]int) int {
  m, n := len(forest), len(forest[0])
  forests := make([][3]int, m * n)
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if forest[i][j] > 1 {
        key :=  i * n + j
        forests[key][0] = i
        forests[key][1] = j
        forests[key][2] = forest[i][j]
      }
    }
  }
  sort.Slice(forests, func(i, j int) bool {
    return forests[i][2] < forests[j][2]
  })
  var getDistance func (sx int, sy int, tx int, ty int) int
  getDistance = func(sx int, sy int, tx int, ty int) int {
    type pair struct {x, y int}
    drs := [][2]int
    visited := make([][]int, m)
    for i := 0; i < m; i++ {
      visited[i] = make([]int, n)
    }
    q, depth := []pair, -1
    for len(q) > 0 {
      l := len(q)
      depth++
      for l > 0 {
        l--
        x, y := q[0].x, q[0].y
        q = q[1:]
        if x == tx && y == ty {
          return depth
        }
        for _, dr := range drs {
          dx, dy := dr[0], dr[1]
          nx, ny := x + dx, y + dy
          if nx < 0 || nx >= m || ny < 0 || ny >= n || forest[nx][ny] == 0 || visited[nx][ny] == 1 {
            continue
          }
          visited[nx][ny] = 1
          q = append(q, pair{nx, ny})
        }
      }
    }
    return -1
  }
  r, t := 0, 0
  for i, f := range forests {
    if i == 0 {
      t = getDistance(0, 0, forests[i][0], forests[i][1])
    } else {
      t = getDistance(forests[i - 1][0], forests[i - 1][1], f[0], f[1])
    } 
    if t == -1 {
      return -1
    } else {
      r += t
    }
  }
  return r
}

class Solution {
  function cutOffTree($forest) {
    $m = count($forest);
    $n = count($forest[0]);
    $forests = [];
    foreach ($forest as $i => $row) {
      foreach ($row as $j => $v) {
        if ($v > 1) $forests []= [$i, $j, $v];
      }
    }
    usort($forests, function ($a, $b) {
      return $a[2] > $b[2];
    });
    $r = 0;
    foreach ($forests as $i => $v) {
      $t = $i === 0 ? $this->getDistance(0, 0, $v[0], $v[1], $m, $n, $forest)
                    : $this->getDistance($forests[$i - 1][0], $forests[$i - 1][1], $v[0], $v[1], $m, $n, $forest);
      if ($t === -1) return -1;
      $r += $t;
    }
    return $r;
  }
  function getDistance($sx, $sy, $tx, $ty, $m, $n, &$forest) {
    $visited = array_fill(0, $m, array_fill(0, $n, 0));
    $drs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    $q = [[$sx, $sy]];
    $depth = -1;
    while (count($q)) {
      $l = count($q);
      $depth++;
      while ($l--) {
        list($x, $y) = array_shift($q);
        if ($x === $tx && $y === $ty) return $depth;
        for ($i = 0; $i < 4; $i++) {
          list($dx, $dy) = $drs[$i];
          $nx = $x + $dx;
          $ny = $y + $dy;
          if ($nx < 0 || $nx >= $m || $ny < 0 || $ny >= $n || $forest[$nx][$ny] === 0 || $visited[$nx][$ny] === 1) continue;
          $visited[$nx][$ny] = 1;
          $q []= [$nx, $ny]; 
        }
      }
    }
    return -1;
  }
}

class Solution:
  def cutOffTree(self, forest: List[List[int]]) -> int:
    m, n = len(forest), len(forest[0])
    forests = []
    for i in range(0, m):
      for j in range(0, n):
        if forest[i][j] > 1: forests.append([i, j, forest[i][j]])
    forests.sort(key = lambda a: a[2])
    drs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    def getDistance(sx, sy, tx, ty):
      q, depth, visited = deque([(sx, sy)]), -1, {(sx, sy)}
      while len(q) > 0:
        l = len(q)
        depth += 1
        while l > 0:
          l -= 1
          x, y = q.popleft()
          if x == tx and y == ty: return depth
          for i in range(0, 4):
            dx, dy = drs[i]
            nx, ny = x + dx, y + dy
            if nx < 0 or nx >= m or ny < 0 or ny >= n or forest[nx][ny] == 0 or (nx, ny) in visited: continue
            visited.add((nx, ny))
            q.append((nx, ny))
      return -1
    preI = preJ = r = 0
    for v in forests:
      i, j = v[0], v[1]
      t = getDistance(preI, preJ, i, j)
      if t == -1: return -1
      r += t
      preI, preJ = i, j
    return r

class Solution {
  public int cutOffTree(List<List<Integer>> forest) {
    int m = forest.size();
    int n = forest.get(0).size();
    List<int[]> forests = new ArrayList<int[]>();
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (forest.get(i).get(j) > 1) forests.add(new int[]{i, j, forest.get(i).get(j)}); 
      }
    }
    Collections.sort(forests, (a, b) -> a[2] - b[2]);
    int r = 0;
    for (int i = 0; i < forests.size(); i++) {
      int t = i == 0 ? getDistance(0, 0, forests.get(i)[0], forests.get(i)[1], m, n, forest)
                     : getDistance(forests.get(i - 1)[0], forests.get(i - 1)[1], forests.get(i)[0], forests.get(i)[1], m, n, forest);
      if (t == -1) return -1;
      r += t;
    }
    return r;
  }
  public int getDistance(int sx, int sy, int tx, int ty, int m, int n, List<List<Integer>> forest) {
    int[][] drs = ;
    Queue<int[]> q = new ArrayDeque<int[]>();
    boolean[][] visited = new boolean[m][n];
    q.offer(new int[]{sx, sy});
    int depth = -1;
    while (q.isEmpty() == false) {
      int l = q.size();
      depth++;
      while (l-- > 0) {
        int[] node = q.poll();
        int x = node[0], y = node[1];
        if (x == tx && y == ty) return depth;
        for (int i = 0; i < 4; i++) {
          int dx = drs[i][0], dy = drs[i][1];
          int nx = x + dx, ny = y + dy;
          if (nx < 0 || nx >= m || ny < 0 || ny >= n || forest.get(nx).get(ny) == 0 || visited[nx][ny] == true) continue;
          visited[nx][ny] = true;
          q.offer(new int[]{nx, ny});
        }
      }
    }
    return -1;
  }
}