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

Mediumgraph-dfs

Pacific Atlantic Water Flow

Problem (yeniden ifade)

m × n yükseklik haritası. Bir hücredeki su, eşit veya daha alçak bir 4-komşuya akabilir. Pasifik üst ve sol kenara, Atlas alt ve sağ kenara değer. Suyun her iki okyanusa da ulaşabileceği hücreleri döndür.

Sezgi

Her hücreden ileri arama O((mn)²). Tersine çevir: bir okyanusa akabilen su, “okyanusun eşit-veya-daha-yüksek hücrelere tırmanması” ile aynıdır. Her okyanusun kenarından içeri DFS, sonra iki ulaşılabilir kümenin kesişimi.

Yaklaşımlar

İki okyanustan DFS

Doğrulanmadı

Zaman O(m·n)Alan O(m·n)

Fikir. pac ve atl boolean ızgaraları. Pasifik kenarlarından (satır 0, sütun 0) ve Atlas kenarlarından (satır m-1, sütun n-1) bir komşuya, heights[next] >= heights[cur] ve henüz görülmediyse DFS. Her iki ızgarada da işaretli hücreler cevap.

Yürüyüş. Zirve ve okyanus-kenarı hücreleri genelde çıkar. Her iki kıyıya tırmanamayan alçak iç çukur çıkmaz.

Trade-off. Her hücre en fazla iki kez (okyanus başına bir) ziyaret edilir, yani doğrusal. Okyanuslardan başlamak püf noktası; her hücreden başlamak TLE olur. Köşe hücreleri her iki okyanusta oturur, her zaman dahildir.

Çözüm

export function pacificAtlantic(heights: number[][]): number[][] {
  if (!heights.length) return [];
  const m = heights.length, n = heights[0]!.length;
  const pac = Array.from({ length: m }, () => Array<boolean>(n).fill(false));
  const atl = Array.from({ length: m }, () => Array<boolean>(n).fill(false));
  const dfs = (r: number, c: number, seen: boolean[][]) => {
    seen[r]![c] = true;
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]] as const) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
      if (seen[nr]![nc] || heights[nr]![nc]! < heights[r]![c]!) continue;
      dfs(nr, nc, seen);
    }
  };
  for (let c = 0; c < n; c++) { dfs(0, c, pac); dfs(m - 1, c, atl); }
  for (let r = 0; r < m; r++) { dfs(r, 0, pac); dfs(r, n - 1, atl); }
  const out: number[][] = [];
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (pac[r]![c] && atl[r]![c]) out.push([r, c]);
  return out;
}

export function pacificAtlantic(heights: number[][]): number[][] {
  if (!heights.length) return [];
  const m = heights.length, n = heights[0]!.length;
  const pac = Array.from({ length: m }, () => Array<boolean>(n).fill(false));
  const atl = Array.from({ length: m }, () => Array<boolean>(n).fill(false));
  const dfs = (r: number, c: number, seen: boolean[][]) => {
    seen[r]![c] = true;
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]] as const) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
      if (seen[nr]![nc] || heights[nr]![nc]! < heights[r]![c]!) continue;
      dfs(nr, nc, seen);
    }
  };
  for (let c = 0; c < n; c++) { dfs(0, c, pac); dfs(m - 1, c, atl); }
  for (let r = 0; r < m; r++) { dfs(r, 0, pac); dfs(r, n - 1, atl); }
  const out: number[][] = [];
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (pac[r]![c] && atl[r]![c]) out.push([r, c]);
  return out;
}

Şablon bağlantısı

Graph DFS’in Pacific-Atlantic şekli: kenarlardan iki ters flood fill, sonra kesişim. LC 733 ile aynı 4-komşu DFS, renk eşleşmesi yerine yükseklik kapısı.

Yansıma

İki okyanusun kıyısından yükseklik artarak DFS. İki kümeye de giren hücreler cevap.
Aşağı değil yukarı: komşu >= ise kıyıdan o hücreye çıkılır. Yalnızca aşağı bakmak iç hücreyi kaçırır.
Tek hücre iki okyanus. Düz plato hepsi. Köşe her iki kıyıya da değer.