Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumshortest-path-weighted

Path With Minimum Effort

Problem (yeniden ifade)

Yükseklik ızgarası. 4-komşuya geçmek mutlak yükseklik farkına mal olur. Bir yolun eforu bu farkların max’ıdır. Sol üstten sağ alta herhangi bir yolun minimum eforunu döndür.

Sezgi

Efor toplam değil darboğaz: bir yol eşik x için uygulanabilir ancak her ardışık çift en fazla x fark ederse. Bu, newDist = max(old, edge) ile Dijkstra, veya x üzerinde ikili arama artı ağırlıksız yürüyüş.

Yaklaşımlar

Max-kenar Dijkstra

Doğrulanmadı

Zaman O(mn log mn)Alan O(mn)

Fikir. dist[r][c] o hücreye min efor. max(d, |h[nr][nc] - h[r][c]|) ile gevşet. Sink ilk pop edildiğinde efor optimal.

Yürüyüş. [[1,2,2],[3,8,2],[5,3,5]]. 1-2-2-2-5 max adım 3; 1-3-5-3-5 max 2. Cevap 2.

Trade-off. LC 743 ile aynı Dijkstra döngüsü; yalnızca gevşetme operatörü değişir. Negatif olmayan “ağırlıklar” (mutlak farklar) greedy değişmezi korur.

Çözüm

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * Dist is the max edge so far, not a sum.
 */
export function minimumEffortPath(heights: number[][]): number {
  const m = heights.length, n = heights[0]!.length;
  const dist = Array.from({ length: m }, () => new Array<number>(n).fill(Infinity));
  dist[0]![0] = 0;
  const pq: [number, number, number][] = [[0, 0, 0]];
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, r, c] = pq.shift()!;
    if (d > dist[r]![c]!) continue;
    if (r === m - 1 && c === n - 1) return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
      const nd = Math.max(d, Math.abs(heights[nr]![nc]! - heights[r]![c]!));
      if (nd < dist[nr]![nc]!) {
        dist[nr]![nc] = nd;
        pq.push([nd, nr, nc]);
      }
    }
  }
  return 0;
}

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * Dist is the max edge so far, not a sum.
 */
export function minimumEffortPath(heights: number[][]): number {
  const m = heights.length, n = heights[0]!.length;
  const dist = Array.from({ length: m }, () => new Array<number>(n).fill(Infinity));
  dist[0]![0] = 0;
  const pq: [number, number, number][] = [[0, 0, 0]];
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, r, c] = pq.shift()!;
    if (d > dist[r]![c]!) continue;
    if (r === m - 1 && c === n - 1) return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
      const nd = Math.max(d, Math.abs(heights[nr]![nc]! - heights[r]![c]!));
      if (nd < dist[nr]![nc]!) {
        dist[nr]![nc] = nd;
        pq.push([nd, nr, nc]);
      }
    }
  }
  return 0;
}

İkili arama + BFS

Doğrulanmadı

Zaman O(mn log H)Alan O(mn)

Fikir. Eforu [0, 10^6] içinde ara. Mid uygulanabilir eğer (0,0)’dan yalnızca |Δh| ≤ mid kenarlarıyla DFS/BFS sink’e varırsa. En küçük uygulanabilir mid’e küçült.

Yürüyüş. Aynı ızgara: mid=1 varamaz; mid=2 varır. Cevap 2.

Trade-off. Binary-search-on-answer’a uyar. Dijkstra’dan fazla kod, fizibilite düz flood fill. H yükseklik aralığı.

Çözüm

export function minimumEffortPath(heights: number[][]): number {
  const m = heights.length, n = heights[0]!.length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  const can = (mid: number): boolean => {
    const seen = Array.from({ length: m }, () => new Array<boolean>(n).fill(false));
    const stack: [number, number][] = [[0, 0]];
    seen[0]![0] = true;
    while (stack.length) {
      const [r, c] = stack.pop()!;
      if (r === m - 1 && c === n - 1) return true;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= m || nc >= n || seen[nr]![nc]) continue;
        if (Math.abs(heights[nr]![nc]! - heights[r]![c]!) > mid) continue;
        seen[nr]![nc] = true;
        stack.push([nr, nc]);
      }
    }
    return false;
  };
  let lo = 0, hi = 1_000_000;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (can(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

export function minimumEffortPath(heights: number[][]): number {
  const m = heights.length, n = heights[0]!.length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  const can = (mid: number): boolean => {
    const seen = Array.from({ length: m }, () => new Array<boolean>(n).fill(false));
    const stack: [number, number][] = [[0, 0]];
    seen[0]![0] = true;
    while (stack.length) {
      const [r, c] = stack.pop()!;
      if (r === m - 1 && c === n - 1) return true;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= m || nc >= n || seen[nr]![nc]) continue;
        if (Math.abs(heights[nr]![nc]! - heights[r]![c]!) > mid) continue;
        seen[nr]![nc] = true;
        stack.push([nr, nc]);
      }
    }
    return false;
  };
  let lo = 0, hi = 1_000_000;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (can(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Şablon bağlantısı

Max-kenar maliyetli Dijkstra, veya cevap üzerinde ikili arama artı BFS. İkisi de kalıp sayfasında; Dijkstra “bu bir en kısa yol” okuması.

Yansıma

Efor, yoldaki en büyük yükseklik farkı. Dijkstra bu eforu minimize eder. İkili arama eşiği, BFS o eforla varışı dener.
Tek hücre 0. Düz ızgara 0. 4 yön. Fark mutlak değer.
Negatif efor yok, Dijkstra geçerli. Eşik büyükse BFS her hücreye varır.