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

Mediumgrid-graph-bfs

Open the Lock

Problem (yeniden ifade)

4 tekerlekli kilit 0000-9999 gösterir. Her hamle bir tekerleği ±1 döndürür. Deadend’lerden kaçın. 0000’dan target’a minimum tur sayısını veya -1 döndür.

Sezgi

Her durumun en fazla 8 komşusu vardır. 0000’dan BFS; deadend’ler başlangıçta visited.

Yaklaşımlar

Kadran durumlarında BFS

Tested only

Time O(10^4)Space O(10^4)

Fikir. (durum, mesafe) kuyruğu. Her tekerlek için ±1 (sarmal); görülen/dead atla.

Adım adım. target 0202, yol üzerindeki engelleyici deadend yoksa genelde 6 tur.

Trade-off’lar. BFS optimal; daha büyük durum uzayında çift yönlü BFS yardımcı olur.

Solution

export function openLock(deadends: string[], target: string): number {
  const dead = new Set(deadends);
  if (dead.has("0000")) return -1;
  if (target === "0000") return 0;
  const q: [string, number][] = [["0000", 0]];
  const seen = new Set<string>(["0000"]);
  const neighbors = (s: string): string[] => {
    const out: string[] = [];
    const a = s.split("");
    for (let i = 0; i < 4; i++) {
      const d = Number(a[i]);
      for (const nd of [(d + 1) % 10, (d + 9) % 10]) {
        a[i] = String(nd);
        out.push(a.join(""));
        a[i] = String(d);
      }
    }
    return out;
  };
  while (q.length) {
    const [cur, dist] = q.shift()!;
    for (const nxt of neighbors(cur)) {
      if (seen.has(nxt) || dead.has(nxt)) continue;
      if (nxt === target) return dist + 1;
      seen.add(nxt);
      q.push([nxt, dist + 1]);
    }
  }
  return -1;
}

export function openLock(deadends: string[], target: string): number {
  const dead = new Set(deadends);
  if (dead.has("0000")) return -1;
  if (target === "0000") return 0;
  const q: [string, number][] = [["0000", 0]];
  const seen = new Set<string>(["0000"]);
  const neighbors = (s: string): string[] => {
    const out: string[] = [];
    const a = s.split("");
    for (let i = 0; i < 4; i++) {
      const d = Number(a[i]);
      for (const nd of [(d + 1) % 10, (d + 9) % 10]) {
        a[i] = String(nd);
        out.push(a.join(""));
        a[i] = String(d);
      }
    }
    return out;
  };
  while (q.length) {
    const [cur, dist] = q.shift()!;
    for (const nxt of neighbors(cur)) {
      if (seen.has(nxt) || dead.has(nxt)) continue;
      if (nxt === target) return dist + 1;
      seen.add(nxt);
      q.push([nxt, dist + 1]);
    }
  }
  return -1;
}

Şablon bağlantısı

Örtük durum grafında Graph BFS.

Yansıma

90 saniyede hangi kalıp bunu ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?