Shortest Paths with BFS
Editorial
A crate of oranges, minute by minute
Rotting Oranges tells its story by the minute: every minute, each fresh orange next to a rotten one rots too. How many minutes until no fresh orange is left, or −1 if one never rots? The way the story is told is the first way anyone writes it: scan the whole crate, find the fresh oranges next to the rot, rot them all at once, count a minute, and scan again, until a scan finds nothing to rot. Here it is on a crate of 150 × 150 oranges, rotten in two opposite corners, beside a BFS that starts from both rotten corners at once:
import time
from collections import deque
R = C = 150 # a crate of 150 x 150 oranges, rotten in two opposite corners
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
crate = [[1] * C for _ in range(R)]
crate[0][0] = crate[R - 1][C - 1] = 2
def next_to_rot(g, r, c):
return any(0 <= r + dr < R and 0 <= c + dc < C and g[r + dr][c + dc] == 2 for dr, dc in DIRS)
def by_rescanning(): # the story as it's told: every minute, scan the whole crate
g = [row[:] for row in crate]
minutes, reads = 0, 0
while True:
rotting = []
for r in range(R):
for c in range(C):
reads += 1
if g[r][c] == 1 and next_to_rot(g, r, c):
rotting.append((r, c))
if not rotting:
break
for r, c in rotting:
g[r][c] = 2
minutes += 1
fresh = sum(row.count(1) for row in g)
return (minutes if fresh == 0 else -1), reads
def by_bfs(): # every rotten orange starts the search at once
g = [row[:] for row in crate]
queue = deque((r, c, 0) for r in range(R) for c in range(C) if g[r][c] == 2)
fresh = sum(row.count(1) for row in g)
minutes, reads = 0, 0
while queue:
r, c, t = queue.popleft()
reads += 1
minutes = max(minutes, t)
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and g[nr][nc] == 1:
g[nr][nc] = 2 # rotten as it goes in, so it goes in once
fresh -= 1
queue.append((nr, nc, t + 1))
return (minutes if fresh == 0 else -1), reads
print(R * C, "oranges, rotten in two corners")
for name, solve in (("rescanning", by_rescanning), ("BFS", by_bfs)):
start = time.perf_counter()
minutes, reads = solve()
ms = round((time.perf_counter() - start) * 1000)
print(f"{name}: {minutes} minutes, {reads} cells read, {ms} ms")
# 22500 oranges, rotten in two corners
# rescanning: 149 minutes, 3375000 cells read, 2400 ms
# BFS: 149 minutes, 22500 cells read, 16 msimport java.util.*;
public class Main {
static final int R = 150, C = 150; // a crate of 150 x 150 oranges, rotten in two opposite corners
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int[][] crate = new int[R][C];
static boolean nextToRot(int[][] g, int r, int c) {
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 2) return true;
}
return false;
}
static int[][] copy() {
int[][] g = new int[R][];
for (int r = 0; r < R; r++) g[r] = crate[r].clone();
return g;
}
static int[] byRescanning() { // the story as it's told: every minute, scan the whole crate
int[][] g = copy();
int minutes = 0, reads = 0;
while (true) {
List<int[]> rotting = new ArrayList<>();
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
reads++;
if (g[r][c] == 1 && nextToRot(g, r, c)) rotting.add(new int[] {r, c});
}
}
if (rotting.isEmpty()) break;
for (int[] p : rotting) g[p[0]][p[1]] = 2;
minutes++;
}
for (int[] row : g) for (int v : row) if (v == 1) return new int[] {-1, reads};
return new int[] {minutes, reads};
}
static int[] byBfs() { // every rotten orange starts the search at once
int[][] g = copy();
ArrayDeque<int[]> queue = new ArrayDeque<>();
int fresh = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (g[r][c] == 2) queue.add(new int[] {r, c, 0});
if (g[r][c] == 1) fresh++;
}
}
int minutes = 0, reads = 0;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
reads++;
minutes = Math.max(minutes, cur[2]);
for (int[] d : DIRS) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 1) {
g[nr][nc] = 2; // rotten as it goes in, so it goes in once
fresh--;
queue.add(new int[] {nr, nc, cur[2] + 1});
}
}
}
return new int[] {fresh == 0 ? minutes : -1, reads};
}
public static void main(String[] args) {
for (int[] row : crate) Arrays.fill(row, 1);
crate[0][0] = 2;
crate[R - 1][C - 1] = 2;
System.out.println(R * C + " oranges, rotten in two corners");
for (String name : new String[] {"rescanning", "BFS"}) {
long start = System.nanoTime();
int[] got = name.equals("BFS") ? byBfs() : byRescanning();
long ms = (System.nanoTime() - start) / 1000000;
System.out.println(name + ": " + got[0] + " minutes, " + got[1] + " cells read, " + ms + " ms");
}
}
}
// 22500 oranges, rotten in two corners
// rescanning: 149 minutes, 3375000 cells read, 52 ms
// BFS: 149 minutes, 22500 cells read, 9 ms#include <bits/stdc++.h>
using namespace std;
const int R = 150, C = 150; // a crate of 150 x 150 oranges, rotten in two opposite corners
const int DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<int>> crate(R, vector<int>(C, 1));
bool nextToRot(const vector<vector<int>>& g, int r, int c) {
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 2) return true;
}
return false;
}
pair<int, int> byRescanning() { // the story as it's told: every minute, scan the whole crate
auto g = crate;
int minutes = 0, reads = 0;
while (true) {
vector<pair<int, int>> rotting;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
reads++;
if (g[r][c] == 1 && nextToRot(g, r, c)) rotting.push_back({r, c});
}
}
if (rotting.empty()) break;
for (auto [r, c] : rotting) g[r][c] = 2;
minutes++;
}
for (auto& row : g) for (int v : row) if (v == 1) return {-1, reads};
return {minutes, reads};
}
pair<int, int> byBfs() { // every rotten orange starts the search at once
auto g = crate;
deque<array<int, 3>> q;
int fresh = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (g[r][c] == 2) q.push_back({r, c, 0});
if (g[r][c] == 1) fresh++;
}
}
int minutes = 0, reads = 0;
while (!q.empty()) {
auto [r, c, t] = q.front();
q.pop_front();
reads++;
minutes = max(minutes, t);
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 1) {
g[nr][nc] = 2; // rotten as it goes in, so it goes in once
fresh--;
q.push_back({nr, nc, t + 1});
}
}
}
return {fresh == 0 ? minutes : -1, reads};
}
int main() {
crate[0][0] = crate[R - 1][C - 1] = 2;
cout << R * C << " oranges, rotten in two corners\n";
for (string name : {"rescanning", "BFS"}) {
auto start = chrono::steady_clock::now();
auto [minutes, reads] = name == "BFS" ? byBfs() : byRescanning();
long long ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
cout << name << ": " << minutes << " minutes, " << reads << " cells read, " << ms << " ms\n";
}
}
// 22500 oranges, rotten in two corners
// rescanning: 149 minutes, 3375000 cells read, 8 ms
// BFS: 149 minutes, 22500 cells read, 0 msconst R = 150, C = 150; // a crate of 150 x 150 oranges, rotten in two opposite corners
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const crate = Array.from({ length: R }, () => new Array(C).fill(1));
crate[0][0] = crate[R - 1][C - 1] = 2;
const nextToRot = (g, r, c) =>
DIRS.some(([dr, dc]) => r + dr >= 0 && r + dr < R && c + dc >= 0 && c + dc < C && g[r + dr][c + dc] === 2);
function byRescanning() { // the story as it's told: every minute, scan the whole crate
const g = crate.map((row) => [...row]);
let minutes = 0, reads = 0;
while (true) {
const rotting = [];
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
reads++;
if (g[r][c] === 1 && nextToRot(g, r, c)) rotting.push([r, c]);
}
}
if (!rotting.length) break;
for (const [r, c] of rotting) g[r][c] = 2;
minutes++;
}
const fresh = g.reduce((n, row) => n + row.filter((v) => v === 1).length, 0);
return [fresh === 0 ? minutes : -1, reads];
}
function byBfs() { // every rotten orange starts the search at once
const g = crate.map((row) => [...row]);
const queue = [];
let fresh = 0;
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (g[r][c] === 2) queue.push([r, c, 0]);
if (g[r][c] === 1) fresh++;
}
}
let minutes = 0, reads = 0;
for (let head = 0; head < queue.length; head++) {
const [r, c, t] = queue[head];
reads++;
minutes = Math.max(minutes, t);
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] === 1) {
g[nr][nc] = 2; // rotten as it goes in, so it goes in once
fresh--;
queue.push([nr, nc, t + 1]);
}
}
}
return [fresh === 0 ? minutes : -1, reads];
}
console.log(`${R * C} oranges, rotten in two corners`);
for (const [name, solve] of [["rescanning", byRescanning], ["BFS", byBfs]]) {
const start = performance.now();
const [minutes, reads] = solve();
console.log(`${name}: ${minutes} minutes, ${reads} cells read, ${Math.round(performance.now() - start)} ms`);
}
// 22500 oranges, rotten in two corners
// rescanning: 149 minutes, 3375000 cells read, 248 ms
// BFS: 149 minutes, 22500 cells read, 33 msconst R = 150, C = 150; // a crate of 150 x 150 oranges, rotten in two opposite corners
const DIRS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const crate: number[][] = Array.from({ length: R }, () => new Array(C).fill(1));
crate[0][0] = crate[R - 1][C - 1] = 2;
const nextToRot = (g: number[][], r: number, c: number): boolean =>
DIRS.some(([dr, dc]) => r + dr >= 0 && r + dr < R && c + dc >= 0 && c + dc < C && g[r + dr][c + dc] === 2);
function byRescanning(): [number, number] { // the story as it's told: every minute, scan the whole crate
const g = crate.map((row) => [...row]);
let minutes = 0, reads = 0;
while (true) {
const rotting: [number, number][] = [];
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
reads++;
if (g[r][c] === 1 && nextToRot(g, r, c)) rotting.push([r, c]);
}
}
if (!rotting.length) break;
for (const [r, c] of rotting) g[r][c] = 2;
minutes++;
}
const fresh = g.reduce((n, row) => n + row.filter((v) => v === 1).length, 0);
return [fresh === 0 ? minutes : -1, reads];
}
function byBfs(): [number, number] { // every rotten orange starts the search at once
const g = crate.map((row) => [...row]);
const queue: [number, number, number][] = [];
let fresh = 0;
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (g[r][c] === 2) queue.push([r, c, 0]);
if (g[r][c] === 1) fresh++;
}
}
let minutes = 0, reads = 0;
for (let head = 0; head < queue.length; head++) {
const [r, c, t] = queue[head];
reads++;
minutes = Math.max(minutes, t);
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] === 1) {
g[nr][nc] = 2; // rotten as it goes in, so it goes in once
fresh--;
queue.push([nr, nc, t + 1]);
}
}
}
return [fresh === 0 ? minutes : -1, reads];
}
console.log(`${R * C} oranges, rotten in two corners`);
const runs: [string, () => [number, number]][] = [["rescanning", byRescanning], ["BFS", byBfs]];
for (const [name, solve] of runs) {
const start = performance.now();
const [minutes, reads] = solve();
console.log(`${name}: ${minutes} minutes, ${reads} cells read, ${Math.round(performance.now() - start)} ms`);
}
// 22500 oranges, rotten in two corners
// rescanning: 149 minutes, 3375000 cells read, 247 ms
// BFS: 149 minutes, 22500 cells read, 32 msusing System;
using System.Collections.Generic;
using System.Diagnostics;
class Program {
const int R = 150, C = 150; // a crate of 150 x 150 oranges, rotten in two opposite corners
static readonly int[][] Dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
static int[,] crate = new int[R, C];
static bool NextToRot(int[,] g, int r, int c) {
foreach (int[] d in Dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr, nc] == 2) return true;
}
return false;
}
static int[] ByRescanning() { // the story as it's told: every minute, scan the whole crate
var g = (int[,]) crate.Clone();
int minutes = 0, reads = 0;
while (true) {
var rotting = new List<int[]>();
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
reads++;
if (g[r, c] == 1 && NextToRot(g, r, c)) rotting.Add(new[] {r, c});
}
}
if (rotting.Count == 0) break;
foreach (int[] p in rotting) g[p[0], p[1]] = 2;
minutes++;
}
foreach (int v in g) if (v == 1) return new[] {-1, reads};
return new[] {minutes, reads};
}
static int[] ByBfs() { // every rotten orange starts the search at once
var g = (int[,]) crate.Clone();
var queue = new Queue<int[]>();
int fresh = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (g[r, c] == 2) queue.Enqueue(new[] {r, c, 0});
if (g[r, c] == 1) fresh++;
}
}
int minutes = 0, reads = 0;
while (queue.Count > 0) {
int[] cur = queue.Dequeue();
reads++;
minutes = Math.Max(minutes, cur[2]);
foreach (int[] d in Dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr, nc] == 1) {
g[nr, nc] = 2; // rotten as it goes in, so it goes in once
fresh--;
queue.Enqueue(new[] {nr, nc, cur[2] + 1});
}
}
}
return new[] {fresh == 0 ? minutes : -1, reads};
}
static void Main() {
for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) crate[r, c] = 1;
crate[0, 0] = 2;
crate[R - 1, C - 1] = 2;
Console.WriteLine($"{R * C} oranges, rotten in two corners");
foreach (string name in new[] {"rescanning", "BFS"}) {
var watch = Stopwatch.StartNew();
int[] got = name == "BFS" ? ByBfs() : ByRescanning();
Console.WriteLine($"{name}: {got[0]} minutes, {got[1]} cells read, {watch.ElapsedMilliseconds} ms");
}
}
}
// 22500 oranges, rotten in two corners
// rescanning: 149 minutes, 3375000 cells read, 79 ms
// BFS: 149 minutes, 22500 cells read, 4 mspackage main
import (
"fmt"
"time"
)
const R, C = 150, 150 // a crate of 150 x 150 oranges, rotten in two opposite corners
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var crate [R][C]int
func nextToRot(g *[R][C]int, r, c int) bool {
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 2 {
return true
}
}
return false
}
func byRescanning() (int, int) { // the story as it's told: every minute, scan the whole crate
g := crate
minutes, reads := 0, 0
for {
rotting := [][2]int{}
for r := 0; r < R; r++ {
for c := 0; c < C; c++ {
reads++
if g[r][c] == 1 && nextToRot(&g, r, c) {
rotting = append(rotting, [2]int{r, c})
}
}
}
if len(rotting) == 0 {
break
}
for _, p := range rotting {
g[p[0]][p[1]] = 2
}
minutes++
}
for _, row := range g {
for _, v := range row {
if v == 1 {
return -1, reads
}
}
}
return minutes, reads
}
func byBfs() (int, int) { // every rotten orange starts the search at once
g := crate
queue := [][3]int{}
fresh := 0
for r := 0; r < R; r++ {
for c := 0; c < C; c++ {
if g[r][c] == 2 {
queue = append(queue, [3]int{r, c, 0})
}
if g[r][c] == 1 {
fresh++
}
}
}
minutes, reads := 0, 0
for head := 0; head < len(queue); head++ {
cur := queue[head]
reads++
if cur[2] > minutes {
minutes = cur[2]
}
for _, d := range dirs {
nr, nc := cur[0]+d[0], cur[1]+d[1]
if nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 1 {
g[nr][nc] = 2 // rotten as it goes in, so it goes in once
fresh--
queue = append(queue, [3]int{nr, nc, cur[2] + 1})
}
}
}
if fresh != 0 {
return -1, reads
}
return minutes, reads
}
func main() {
for r := range crate {
for c := range crate[r] {
crate[r][c] = 1
}
}
crate[0][0], crate[R-1][C-1] = 2, 2
fmt.Printf("%d oranges, rotten in two corners\n", R*C)
for _, name := range []string{"rescanning", "BFS"} {
start := time.Now()
var minutes, reads int
if name == "BFS" {
minutes, reads = byBfs()
} else {
minutes, reads = byRescanning()
}
fmt.Printf("%s: %d minutes, %d cells read, %d ms\n", name, minutes, reads, time.Since(start).Milliseconds())
}
}
// 22500 oranges, rotten in two corners
// rescanning: 149 minutes, 3375000 cells read, 19 ms
// BFS: 149 minutes, 22500 cells read, 3 msBoth answer 149 minutes in every language. Rescanning read 3,375,000 cells: the whole crate of 22,500, 150 times, once a minute and once more to find nothing left to rot. BFS read each orange once, 22,500 in all. In Python that was 2,400 ms against 16 ms, and BFS was faster in every language.
They agree because BFS's layers are the minutes. The rotten oranges go in the queue first, as layer 0. The fresh oranges next to them are layer 1, and rot in minute 1; the fresh ones next to those are layer 2, and so on. The minute an orange rots is its distance, in steps through fresh oranges, from the nearest rotten one. So the answer is the largest distance, or −1 when some fresh orange is never reached: one pass over the crate, O(R × C), instead of a scan every minute.
Why the first arrival is the fewest steps
BFS takes vertices off its queue in order of their distance from the start: every vertex 1 edge away comes off before any vertex 2 edges away, and so on. A vertex goes in only when a vertex one edge closer comes out, so the queue only ever holds one layer followed by the next. The first time BFS reaches a vertex is therefore by the fewest edges, and its distance is one more than the distance of the vertex that found it. Keep that vertex too, as its parent, and the path itself reads back from the end, parent by parent.
Shortest Path in Unweighted Graph asks for exactly those distances. Shortest Path in Binary Matrix is the same search on a grid where a move can go in any of eight directions, diagonals included, and the answer counts the cells on the path. Both here: 8 stations joined by lines, and a grid of 5 × 5 cells where 0 is open:
from collections import deque
n = 8 # stations, and the lines between them
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 6), (5, 7), (6, 7)]
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
dist, parent = [-1] * n, [-1] * n
dist[0] = 0
queue = deque([0])
while queue:
u = queue.popleft()
for v in graph[u]:
if dist[v] == -1: # the first time v is reached is by the fewest edges
dist[v], parent[v] = dist[u] + 1, u
queue.append(v)
print("stops from 0:", " ".join(map(str, dist)))
route, v = [], 7
while v != -1: # read the route back from the end
route.append(v)
v = parent[v]
print("a fewest-stops route to 7:", " ".join(map(str, route[::-1])))
grid = ["00100", # Shortest Path in Binary Matrix: 0 is open, eight moves
"01010",
"00010",
"11000",
"00110"]
N = len(grid)
cells = [[0] * N for _ in range(N)] # a path's length in cells, 0 for a cell not reached
cells[0][0] = 1
queue = deque([(0, 0)])
while queue:
r, c = queue.popleft()
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N and grid[nr][nc] == "0" and cells[nr][nc] == 0:
cells[nr][nc] = cells[r][c] + 1
queue.append((nr, nc))
print("corner to corner in eight moves:", cells[N - 1][N - 1], "cells")
# stops from 0: 0 1 1 2 2 3 3 4
# a fewest-stops route to 7: 0 1 3 5 7
# corner to corner in eight moves: 6 cellsimport java.util.*;
public class Main {
public static void main(String[] args) {
int n = 8; // stations, and the lines between them
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 6}, {5, 7}, {6, 7}};
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] e : edges) {
graph.get(e[0]).add(e[1]);
graph.get(e[1]).add(e[0]);
}
int[] dist = new int[n], parent = new int[n];
Arrays.fill(dist, -1);
Arrays.fill(parent, -1);
dist[0] = 0;
ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.add(0);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph.get(u)) {
if (dist[v] == -1) { // the first time v is reached is by the fewest edges
dist[v] = dist[u] + 1;
parent[v] = u;
queue.add(v);
}
}
}
StringJoiner stops = new StringJoiner(" ");
for (int d : dist) stops.add(String.valueOf(d));
System.out.println("stops from 0: " + stops);
LinkedList<Integer> route = new LinkedList<>();
for (int v = 7; v != -1; v = parent[v]) route.addFirst(v); // read the route back from the end
StringJoiner shown = new StringJoiner(" ");
for (int v : route) shown.add(String.valueOf(v));
System.out.println("a fewest-stops route to 7: " + shown);
String[] grid = {"00100", // Shortest Path in Binary Matrix: 0 is open, eight moves
"01010",
"00010",
"11000",
"00110"};
int N = grid.length;
int[][] cells = new int[N][N]; // a path's length in cells, 0 for a cell not reached
cells[0][0] = 1;
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[] {0, 0});
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
int nr = cur[0] + dr, nc = cur[1] + dc;
if (nr >= 0 && nr < N && nc >= 0 && nc < N && grid[nr].charAt(nc) == '0' && cells[nr][nc] == 0) {
cells[nr][nc] = cells[cur[0]][cur[1]] + 1;
q.add(new int[] {nr, nc});
}
}
}
}
System.out.println("corner to corner in eight moves: " + cells[N - 1][N - 1] + " cells");
}
}
// stops from 0: 0 1 1 2 2 3 3 4
// a fewest-stops route to 7: 0 1 3 5 7
// corner to corner in eight moves: 6 cells#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 8; // stations, and the lines between them
vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 6}, {5, 7}, {6, 7}};
vector<vector<int>> graph(n);
for (auto [u, v] : edges) {
graph[u].push_back(v);
graph[v].push_back(u);
}
vector<int> dist(n, -1), parent(n, -1);
dist[0] = 0;
queue<int> q;
q.push(0);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (dist[v] == -1) { // the first time v is reached is by the fewest edges
dist[v] = dist[u] + 1;
parent[v] = u;
q.push(v);
}
}
}
cout << "stops from 0:";
for (int d : dist) cout << " " << d;
cout << "\n";
vector<int> route;
for (int v = 7; v != -1; v = parent[v]) route.insert(route.begin(), v); // read the route back from the end
cout << "a fewest-stops route to 7:";
for (int v : route) cout << " " << v;
cout << "\n";
vector<string> grid = {"00100", // Shortest Path in Binary Matrix: 0 is open, eight moves
"01010",
"00010",
"11000",
"00110"};
int N = grid.size();
vector<vector<int>> cells(N, vector<int>(N, 0)); // a path's length in cells, 0 for a cell not reached
cells[0][0] = 1;
queue<pair<int, int>> g;
g.push({0, 0});
while (!g.empty()) {
auto [r, c] = g.front();
g.pop();
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < N && nc >= 0 && nc < N && grid[nr][nc] == '0' && cells[nr][nc] == 0) {
cells[nr][nc] = cells[r][c] + 1;
g.push({nr, nc});
}
}
}
}
cout << "corner to corner in eight moves: " << cells[N - 1][N - 1] << " cells\n";
}
// stops from 0: 0 1 1 2 2 3 3 4
// a fewest-stops route to 7: 0 1 3 5 7
// corner to corner in eight moves: 6 cellsconst n = 8; // stations, and the lines between them
const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 7]];
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const dist = new Array(n).fill(-1), parent = new Array(n).fill(-1);
dist[0] = 0;
const queue = [0];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
for (const v of graph[u]) {
if (dist[v] === -1) { // the first time v is reached is by the fewest edges
dist[v] = dist[u] + 1;
parent[v] = u;
queue.push(v);
}
}
}
console.log(`stops from 0: ${dist.join(" ")}`);
const route = [];
for (let v = 7; v !== -1; v = parent[v]) route.unshift(v); // read the route back from the end
console.log(`a fewest-stops route to 7: ${route.join(" ")}`);
const grid = ["00100", // Shortest Path in Binary Matrix: 0 is open, eight moves
"01010",
"00010",
"11000",
"00110"];
const N = grid.length;
const cells = Array.from({ length: N }, () => new Array(N).fill(0)); // a path's length in cells, 0: not reached
cells[0][0] = 1;
const q = [[0, 0]];
for (let head = 0; head < q.length; head++) {
const [r, c] = q[head];
for (let dr = -1; dr <= 1; dr++) {
for (let dc = -1; dc <= 1; dc++) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < N && nc >= 0 && nc < N && grid[nr][nc] === "0" && cells[nr][nc] === 0) {
cells[nr][nc] = cells[r][c] + 1;
q.push([nr, nc]);
}
}
}
}
console.log(`corner to corner in eight moves: ${cells[N - 1][N - 1]} cells`);
// stops from 0: 0 1 1 2 2 3 3 4
// a fewest-stops route to 7: 0 1 3 5 7
// corner to corner in eight moves: 6 cellsconst n = 8; // stations, and the lines between them
const edges: [number, number][] = [[0, 1], [0, 2], [1, 3], [2, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 7]];
const graph: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const dist: number[] = new Array(n).fill(-1), parent: number[] = new Array(n).fill(-1);
dist[0] = 0;
const queue: number[] = [0];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
for (const v of graph[u]) {
if (dist[v] === -1) { // the first time v is reached is by the fewest edges
dist[v] = dist[u] + 1;
parent[v] = u;
queue.push(v);
}
}
}
console.log(`stops from 0: ${dist.join(" ")}`);
const route: number[] = [];
for (let v = 7; v !== -1; v = parent[v]) route.unshift(v); // read the route back from the end
console.log(`a fewest-stops route to 7: ${route.join(" ")}`);
const grid: string[] = ["00100", // Shortest Path in Binary Matrix: 0 is open, eight moves
"01010",
"00010",
"11000",
"00110"];
const N = grid.length;
const cells: number[][] = Array.from({ length: N }, () => new Array(N).fill(0)); // 0 for a cell not reached
cells[0][0] = 1;
const q: [number, number][] = [[0, 0]];
for (let head = 0; head < q.length; head++) {
const [r, c] = q[head];
for (let dr = -1; dr <= 1; dr++) {
for (let dc = -1; dc <= 1; dc++) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < N && nc >= 0 && nc < N && grid[nr][nc] === "0" && cells[nr][nc] === 0) {
cells[nr][nc] = cells[r][c] + 1;
q.push([nr, nc]);
}
}
}
}
console.log(`corner to corner in eight moves: ${cells[N - 1][N - 1]} cells`);
// stops from 0: 0 1 1 2 2 3 3 4
// a fewest-stops route to 7: 0 1 3 5 7
// corner to corner in eight moves: 6 cellsusing System;
using System.Collections.Generic;
class Program {
static void Main() {
int n = 8; // stations, and the lines between them
int[][] edges = { new[] {0, 1}, new[] {0, 2}, new[] {1, 3}, new[] {2, 3}, new[] {2, 4}, new[] {3, 5},
new[] {4, 6}, new[] {5, 7}, new[] {6, 7} };
var graph = new List<int>[n];
for (int i = 0; i < n; i++) graph[i] = new List<int>();
foreach (int[] e in edges) {
graph[e[0]].Add(e[1]);
graph[e[1]].Add(e[0]);
}
var dist = new int[n];
var parent = new int[n];
for (int i = 0; i < n; i++) dist[i] = parent[i] = -1;
dist[0] = 0;
var queue = new Queue<int>();
queue.Enqueue(0);
while (queue.Count > 0) {
int u = queue.Dequeue();
foreach (int v in graph[u]) {
if (dist[v] == -1) { // the first time v is reached is by the fewest edges
dist[v] = dist[u] + 1;
parent[v] = u;
queue.Enqueue(v);
}
}
}
Console.WriteLine("stops from 0: " + string.Join(" ", dist));
var route = new List<int>();
for (int v = 7; v != -1; v = parent[v]) route.Insert(0, v); // read the route back from the end
Console.WriteLine("a fewest-stops route to 7: " + string.Join(" ", route));
string[] grid = {"00100", // Shortest Path in Binary Matrix: 0 is open, eight moves
"01010",
"00010",
"11000",
"00110"};
int N = grid.Length;
var cells = new int[N, N]; // a path's length in cells, 0 for a cell not reached
cells[0, 0] = 1;
var q = new Queue<int[]>();
q.Enqueue(new[] {0, 0});
while (q.Count > 0) {
int[] cur = q.Dequeue();
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
int nr = cur[0] + dr, nc = cur[1] + dc;
if (nr >= 0 && nr < N && nc >= 0 && nc < N && grid[nr][nc] == '0' && cells[nr, nc] == 0) {
cells[nr, nc] = cells[cur[0], cur[1]] + 1;
q.Enqueue(new[] {nr, nc});
}
}
}
}
Console.WriteLine($"corner to corner in eight moves: {cells[N - 1, N - 1]} cells");
}
}
// stops from 0: 0 1 1 2 2 3 3 4
// a fewest-stops route to 7: 0 1 3 5 7
// corner to corner in eight moves: 6 cellspackage main
import (
"fmt"
"strconv"
"strings"
)
func joined(values []int) string {
parts := make([]string, len(values))
for i, v := range values {
parts[i] = strconv.Itoa(v)
}
return strings.Join(parts, " ")
}
func main() {
n := 8 // stations, and the lines between them
edges := [][2]int{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 6}, {5, 7}, {6, 7}}
graph := make([][]int, n)
for _, e := range edges {
graph[e[0]] = append(graph[e[0]], e[1])
graph[e[1]] = append(graph[e[1]], e[0])
}
dist, parent := make([]int, n), make([]int, n)
for i := range dist {
dist[i], parent[i] = -1, -1
}
dist[0] = 0
queue := []int{0}
for head := 0; head < len(queue); head++ {
u := queue[head]
for _, v := range graph[u] {
if dist[v] == -1 { // the first time v is reached is by the fewest edges
dist[v], parent[v] = dist[u]+1, u
queue = append(queue, v)
}
}
}
fmt.Println("stops from 0: " + joined(dist))
route := []int{}
for v := 7; v != -1; v = parent[v] { // read the route back from the end
route = append([]int{v}, route...)
}
fmt.Println("a fewest-stops route to 7: " + joined(route))
grid := []string{ // Shortest Path in Binary Matrix: 0 is open, eight moves
"00100",
"01010",
"00010",
"11000",
"00110",
}
N := len(grid)
cells := make([][]int, N) // a path's length in cells, 0 for a cell not reached
for i := range cells {
cells[i] = make([]int, N)
}
cells[0][0] = 1
q := [][2]int{{0, 0}}
for head := 0; head < len(q); head++ {
r, c := q[head][0], q[head][1]
for dr := -1; dr <= 1; dr++ {
for dc := -1; dc <= 1; dc++ {
nr, nc := r+dr, c+dc
if nr >= 0 && nr < N && nc >= 0 && nc < N && grid[nr][nc] == '0' && cells[nr][nc] == 0 {
cells[nr][nc] = cells[r][c] + 1
q = append(q, [2]int{nr, nc})
}
}
}
}
fmt.Printf("corner to corner in eight moves: %d cells\n", cells[N-1][N-1])
}
// stops from 0: 0 1 1 2 2 3 3 4
// a fewest-stops route to 7: 0 1 3 5 7
// corner to corner in eight moves: 6 cellsStation 7 is 4 stops from 0. Reading parents back from 7 gives 0, 1, 3, 5, 7, one of several routes of 4 stops (0, 2, 4, 6, 7 is another); BFS keeps whichever reached each station first. The grid's way from corner to corner is 6 cells long. A vertex the search never reaches keeps −1 in the list, and a grid cell keeps 0.
All of this needs every edge to count the same. Give edges different costs and a vertex reached in fewer edges can still cost more: that's Weighted Shortest Paths: Dijkstra, Bellman-Ford and Floyd-Warshall, and the case where every edge costs 0 or 1 is further down this page.
Many starts at once
Rotting Oranges started from two rotten corners at once. That's the general trick: when the question is the distance to the nearest of many sources, put every source in the queue at the start, all at distance 0. It's one BFS, as if from one extra vertex joined to every source, and each cell's first arrival comes from its nearest source. A search from each source would give the same answers for k times the work.
01 Matrix asks for every cell's distance to its nearest 0. Walls and Gates asks for every empty room's distance to its nearest gate, walking through empty rooms only. One function does both, told which cells are sources and which can be entered:
from collections import deque
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
def nearest(grid, is_source, can_enter): # every source at distance 0, all of them in the queue at once
R, C = len(grid), len(grid[0])
dist = [[-1] * C for _ in range(R)]
queue = deque()
for r in range(R):
for c in range(C):
if is_source(grid[r][c]):
dist[r][c] = 0
queue.append((r, c))
while queue:
r, c = queue.popleft()
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] == -1 and can_enter(grid[nr][nc]):
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return dist
mat = [[1, 1, 1, 0], # 01 Matrix: each cell's steps to its nearest 0
[1, 1, 1, 1],
[0, 1, 1, 1]]
print("01 Matrix:")
for row in nearest(mat, lambda v: v == 0, lambda v: True):
print(" ".join(map(str, row)))
INF = 2147483647
rooms = [[0, INF, INF, -1], # Walls and Gates: -1 a wall, 0 a gate, INF an empty room
[-1, -1, INF, INF],
[INF, -1, INF, 0]]
dist = nearest(rooms, lambda v: v == 0, lambda v: v == INF)
print("Walls and Gates:")
for r, row in enumerate(rooms):
print(" ".join("#" if v == -1 else str(dist[r][c]) if dist[r][c] >= 0 else "INF" for c, v in enumerate(row)))
# 01 Matrix:
# 2 2 1 0
# 1 2 2 1
# 0 1 2 2
# Walls and Gates:
# 0 1 2 #
# # # 2 1
# INF # 1 0import java.util.*;
import java.util.function.IntPredicate;
public class Main {
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int[][] nearest(int[][] grid, IntPredicate isSource, IntPredicate canEnter) { // all sources at once
int R = grid.length, C = grid[0].length;
int[][] dist = new int[R][C];
ArrayDeque<int[]> queue = new ArrayDeque<>();
for (int r = 0; r < R; r++) {
Arrays.fill(dist[r], -1);
for (int c = 0; c < C; c++) {
if (isSource.test(grid[r][c])) {
dist[r][c] = 0;
queue.add(new int[] {r, c});
}
}
}
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int[] d : DIRS) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && dist[nr][nc] == -1 && canEnter.test(grid[nr][nc])) {
dist[nr][nc] = dist[cur[0]][cur[1]] + 1;
queue.add(new int[] {nr, nc});
}
}
}
return dist;
}
public static void main(String[] args) {
int[][] mat = {{1, 1, 1, 0}, // 01 Matrix: each cell's steps to its nearest 0
{1, 1, 1, 1},
{0, 1, 1, 1}};
System.out.println("01 Matrix:");
for (int[] row : nearest(mat, v -> v == 0, v -> true)) {
StringJoiner s = new StringJoiner(" ");
for (int v : row) s.add(String.valueOf(v));
System.out.println(s);
}
final int INF = 2147483647;
int[][] rooms = {{0, INF, INF, -1}, // Walls and Gates: -1 a wall, 0 a gate, INF an empty room
{-1, -1, INF, INF},
{INF, -1, INF, 0}};
int[][] dist = nearest(rooms, v -> v == 0, v -> v == INF);
System.out.println("Walls and Gates:");
for (int r = 0; r < rooms.length; r++) {
StringJoiner s = new StringJoiner(" ");
for (int c = 0; c < rooms[r].length; c++) {
s.add(rooms[r][c] == -1 ? "#" : dist[r][c] >= 0 ? String.valueOf(dist[r][c]) : "INF");
}
System.out.println(s);
}
}
}
// 01 Matrix:
// 2 2 1 0
// 1 2 2 1
// 0 1 2 2
// Walls and Gates:
// 0 1 2 #
// # # 2 1
// INF # 1 0#include <bits/stdc++.h>
using namespace std;
const int DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<int>> nearest(const vector<vector<int>>& grid, function<bool(int)> isSource,
function<bool(int)> canEnter) { // every source at distance 0, all at once
int R = grid.size(), C = grid[0].size();
vector<vector<int>> dist(R, vector<int>(C, -1));
queue<pair<int, int>> q;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (isSource(grid[r][c])) {
dist[r][c] = 0;
q.push({r, c});
}
}
}
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && dist[nr][nc] == -1 && canEnter(grid[nr][nc])) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
return dist;
}
int main() {
vector<vector<int>> mat = {{1, 1, 1, 0}, // 01 Matrix: each cell's steps to its nearest 0
{1, 1, 1, 1},
{0, 1, 1, 1}};
cout << "01 Matrix:\n";
for (auto& row : nearest(mat, [](int v) { return v == 0; }, [](int) { return true; })) {
for (size_t c = 0; c < row.size(); c++) cout << (c ? " " : "") << row[c];
cout << "\n";
}
const int INF = 2147483647;
vector<vector<int>> rooms = {{0, INF, INF, -1}, // Walls and Gates: -1 a wall, 0 a gate, INF an empty room
{-1, -1, INF, INF},
{INF, -1, INF, 0}};
auto dist = nearest(rooms, [](int v) { return v == 0; }, [&](int v) { return v == INF; });
cout << "Walls and Gates:\n";
for (size_t r = 0; r < rooms.size(); r++) {
for (size_t c = 0; c < rooms[r].size(); c++) {
cout << (c ? " " : "");
if (rooms[r][c] == -1) cout << "#";
else if (dist[r][c] >= 0) cout << dist[r][c];
else cout << "INF";
}
cout << "\n";
}
}
// 01 Matrix:
// 2 2 1 0
// 1 2 2 1
// 0 1 2 2
// Walls and Gates:
// 0 1 2 #
// # # 2 1
// INF # 1 0const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function nearest(grid, isSource, canEnter) { // every source at distance 0, all of them in the queue at once
const R = grid.length, C = grid[0].length;
const dist = Array.from({ length: R }, () => new Array(C).fill(-1));
const queue = [];
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (isSource(grid[r][c])) {
dist[r][c] = 0;
queue.push([r, c]);
}
}
}
for (let head = 0; head < queue.length; head++) {
const [r, c] = queue[head];
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && dist[nr][nc] === -1 && canEnter(grid[nr][nc])) {
dist[nr][nc] = dist[r][c] + 1;
queue.push([nr, nc]);
}
}
}
return dist;
}
const mat = [[1, 1, 1, 0], // 01 Matrix: each cell's steps to its nearest 0
[1, 1, 1, 1],
[0, 1, 1, 1]];
console.log("01 Matrix:");
for (const row of nearest(mat, (v) => v === 0, () => true)) console.log(row.join(" "));
const INF = 2147483647;
const rooms = [[0, INF, INF, -1], // Walls and Gates: -1 a wall, 0 a gate, INF an empty room
[-1, -1, INF, INF],
[INF, -1, INF, 0]];
const dist = nearest(rooms, (v) => v === 0, (v) => v === INF);
console.log("Walls and Gates:");
rooms.forEach((row, r) => {
console.log(row.map((v, c) => (v === -1 ? "#" : dist[r][c] >= 0 ? String(dist[r][c]) : "INF")).join(" "));
});
// 01 Matrix:
// 2 2 1 0
// 1 2 2 1
// 0 1 2 2
// Walls and Gates:
// 0 1 2 #
// # # 2 1
// INF # 1 0const DIRS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function nearest(grid: number[][], isSource: (v: number) => boolean, canEnter: (v: number) => boolean): number[][] {
const R = grid.length, C = grid[0].length; // every source at distance 0, all of them in the queue at once
const dist: number[][] = Array.from({ length: R }, () => new Array(C).fill(-1));
const queue: [number, number][] = [];
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (isSource(grid[r][c])) {
dist[r][c] = 0;
queue.push([r, c]);
}
}
}
for (let head = 0; head < queue.length; head++) {
const [r, c] = queue[head];
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && dist[nr][nc] === -1 && canEnter(grid[nr][nc])) {
dist[nr][nc] = dist[r][c] + 1;
queue.push([nr, nc]);
}
}
}
return dist;
}
const mat: number[][] = [[1, 1, 1, 0], // 01 Matrix: each cell's steps to its nearest 0
[1, 1, 1, 1],
[0, 1, 1, 1]];
console.log("01 Matrix:");
for (const row of nearest(mat, (v) => v === 0, () => true)) console.log(row.join(" "));
const INF = 2147483647;
const rooms: number[][] = [[0, INF, INF, -1], // Walls and Gates: -1 a wall, 0 a gate, INF an empty room
[-1, -1, INF, INF],
[INF, -1, INF, 0]];
const dist = nearest(rooms, (v) => v === 0, (v) => v === INF);
console.log("Walls and Gates:");
rooms.forEach((row, r) => {
console.log(row.map((v, c) => (v === -1 ? "#" : dist[r][c] >= 0 ? String(dist[r][c]) : "INF")).join(" "));
});
// 01 Matrix:
// 2 2 1 0
// 1 2 2 1
// 0 1 2 2
// Walls and Gates:
// 0 1 2 #
// # # 2 1
// INF # 1 0using System;
using System.Collections.Generic;
class Program {
static readonly int[][] Dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
static int[,] Nearest(int[,] grid, Func<int, bool> isSource, Func<int, bool> canEnter) { // all sources at once
int R = grid.GetLength(0), C = grid.GetLength(1);
var dist = new int[R, C];
var queue = new Queue<int[]>();
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
dist[r, c] = -1;
if (isSource(grid[r, c])) {
dist[r, c] = 0;
queue.Enqueue(new[] {r, c});
}
}
}
while (queue.Count > 0) {
int[] cur = queue.Dequeue();
foreach (int[] d in Dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && dist[nr, nc] == -1 && canEnter(grid[nr, nc])) {
dist[nr, nc] = dist[cur[0], cur[1]] + 1;
queue.Enqueue(new[] {nr, nc});
}
}
}
return dist;
}
static void Main() {
int[,] mat = { {1, 1, 1, 0}, // 01 Matrix: each cell's steps to its nearest 0
{1, 1, 1, 1},
{0, 1, 1, 1} };
var near = Nearest(mat, v => v == 0, v => true);
Console.WriteLine("01 Matrix:");
for (int r = 0; r < 3; r++) {
var row = new List<int>();
for (int c = 0; c < 4; c++) row.Add(near[r, c]);
Console.WriteLine(string.Join(" ", row));
}
const int INF = 2147483647;
int[,] rooms = { {0, INF, INF, -1}, // Walls and Gates: -1 a wall, 0 a gate, INF an empty room
{-1, -1, INF, INF},
{INF, -1, INF, 0} };
var dist = Nearest(rooms, v => v == 0, v => v == INF);
Console.WriteLine("Walls and Gates:");
for (int r = 0; r < 3; r++) {
var row = new List<string>();
for (int c = 0; c < 4; c++) row.Add(rooms[r, c] == -1 ? "#" : dist[r, c] >= 0 ? dist[r, c].ToString() : "INF");
Console.WriteLine(string.Join(" ", row));
}
}
}
// 01 Matrix:
// 2 2 1 0
// 1 2 2 1
// 0 1 2 2
// Walls and Gates:
// 0 1 2 #
// # # 2 1
// INF # 1 0package main
import (
"fmt"
"strconv"
"strings"
)
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func nearest(grid [][]int, isSource, canEnter func(int) bool) [][]int { // every source at distance 0, all at once
R, C := len(grid), len(grid[0])
dist := make([][]int, R)
queue := [][2]int{}
for r := 0; r < R; r++ {
dist[r] = make([]int, C)
for c := 0; c < C; c++ {
dist[r][c] = -1
if isSource(grid[r][c]) {
dist[r][c] = 0
queue = append(queue, [2]int{r, c})
}
}
}
for head := 0; head < len(queue); head++ {
r, c := queue[head][0], queue[head][1]
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < R && nc >= 0 && nc < C && dist[nr][nc] == -1 && canEnter(grid[nr][nc]) {
dist[nr][nc] = dist[r][c] + 1
queue = append(queue, [2]int{nr, nc})
}
}
}
return dist
}
func main() {
mat := [][]int{ // 01 Matrix: each cell's steps to its nearest 0
{1, 1, 1, 0},
{1, 1, 1, 1},
{0, 1, 1, 1},
}
fmt.Println("01 Matrix:")
for _, row := range nearest(mat, func(v int) bool { return v == 0 }, func(int) bool { return true }) {
parts := []string{}
for _, v := range row {
parts = append(parts, strconv.Itoa(v))
}
fmt.Println(strings.Join(parts, " "))
}
const INF = 2147483647
rooms := [][]int{ // Walls and Gates: -1 a wall, 0 a gate, INF an empty room
{0, INF, INF, -1},
{-1, -1, INF, INF},
{INF, -1, INF, 0},
}
dist := nearest(rooms, func(v int) bool { return v == 0 }, func(v int) bool { return v == INF })
fmt.Println("Walls and Gates:")
for r, row := range rooms {
parts := []string{}
for c, v := range row {
switch {
case v == -1:
parts = append(parts, "#")
case dist[r][c] >= 0:
parts = append(parts, strconv.Itoa(dist[r][c]))
default:
parts = append(parts, "INF")
}
}
fmt.Println(strings.Join(parts, " "))
}
}
// 01 Matrix:
// 2 2 1 0
// 1 2 2 1
// 0 1 2 2
// Walls and Gates:
// 0 1 2 #
// # # 2 1
// INF # 1 0In the matrix every 0 is a source, and the 1s get 1 or 2. In the rooms both gates spread at once; the room at the bottom left stays INF, closed in by walls, because no search reaches it. Each grid is one pass, O(R × C), however many sources it has.
Spread the Rot. Be the search yourself: each minute, pick the oranges that rot next, from every rotten one at once, and see how many minutes the crate takes.
Searching states, not places
Some graphs are never drawn. In Open the Lock four wheels start at 0000, a move turns one wheel one notch up or down, and some combinations are dead ends that jam the lock. The vertices are the 10,000 combinations and the edges are the 8 moves out of each, and nothing needs storing: the search makes a combination's neighbours when it comes off the queue. Word Ladder goes from one word to another changing one letter at a time, with every word on the way from a list; the vertices are the words. In both, BFS's distance is the fewest moves:
from collections import deque
def open_lock(deadends, target): # a state is the four digits; a move turns one wheel up or down
dead = set(deadends)
if "0000" in dead:
return -1
dist = {"0000": 0}
queue = deque(["0000"])
while queue:
s = queue.popleft()
if s == target:
return dist[s]
for i in range(4):
for step in (1, -1):
t = s[:i] + str((int(s[i]) + step) % 10) + s[i + 1:]
if t not in dead and t not in dist:
dist[t] = dist[s] + 1
queue.append(t)
return -1
def ladder(begin, end, words): # a state is a word; a move changes one letter into another word
words = set(words)
parent = {begin: None}
queue = deque([begin])
while queue:
w = queue.popleft()
if w == end:
path = []
while w is not None:
path.append(w)
w = parent[w]
return path[::-1]
for i in range(len(w)):
for ch in "abcdefghijklmnopqrstuvwxyz":
t = w[:i] + ch + w[i + 1:]
if t in words and t not in parent:
parent[t] = w
queue.append(t)
return []
print("turns from 0000 to 2020:", open_lock(["1000", "0010", "9000", "0090"], "2020"))
path = ladder("cold", "warm", ["bold", "cord", "card", "ward", "warm", "worm", "word", "wore", "core", "corm"])
print("cold to warm:", len(path), "words:", " ".join(path))
# turns from 0000 to 2020: 6
# cold to warm: 5 words: cold cord word ward warmimport java.util.*;
public class Main {
static int openLock(String[] deadends, String target) { // a state is the four digits; a move turns one wheel
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
if (dead.contains("0000")) return -1;
Map<String, Integer> dist = new HashMap<>();
dist.put("0000", 0);
ArrayDeque<String> queue = new ArrayDeque<>();
queue.add("0000");
while (!queue.isEmpty()) {
String s = queue.poll();
if (s.equals(target)) return dist.get(s);
for (int i = 0; i < 4; i++) {
for (int step : new int[] {1, -1}) {
char[] t = s.toCharArray();
t[i] = (char) ('0' + ((t[i] - '0' + step + 10) % 10));
String next = new String(t);
if (!dead.contains(next) && !dist.containsKey(next)) {
dist.put(next, dist.get(s) + 1);
queue.add(next);
}
}
}
}
return -1;
}
static List<String> ladder(String begin, String end, String[] list) { // a state is a word; a move changes a letter
Set<String> words = new HashSet<>(Arrays.asList(list));
Map<String, String> parent = new HashMap<>();
parent.put(begin, null);
ArrayDeque<String> queue = new ArrayDeque<>();
queue.add(begin);
while (!queue.isEmpty()) {
String w = queue.poll();
if (w.equals(end)) {
LinkedList<String> path = new LinkedList<>();
for (String x = w; x != null; x = parent.get(x)) path.addFirst(x);
return path;
}
for (int i = 0; i < w.length(); i++) {
for (char ch = 'a'; ch <= 'z'; ch++) {
String t = w.substring(0, i) + ch + w.substring(i + 1);
if (words.contains(t) && !parent.containsKey(t)) {
parent.put(t, w);
queue.add(t);
}
}
}
}
return new ArrayList<>();
}
public static void main(String[] args) {
System.out.println("turns from 0000 to 2020: " + openLock(new String[] {"1000", "0010", "9000", "0090"}, "2020"));
List<String> path = ladder("cold", "warm",
new String[] {"bold", "cord", "card", "ward", "warm", "worm", "word", "wore", "core", "corm"});
System.out.println("cold to warm: " + path.size() + " words: " + String.join(" ", path));
}
}
// turns from 0000 to 2020: 6
// cold to warm: 5 words: cold cord word ward warm#include <bits/stdc++.h>
using namespace std;
int openLock(const vector<string>& deadends, const string& target) { // a state is the four digits; a move turns a wheel
unordered_set<string> dead(deadends.begin(), deadends.end());
if (dead.count("0000")) return -1;
unordered_map<string, int> dist = {{"0000", 0}};
queue<string> q;
q.push("0000");
while (!q.empty()) {
string s = q.front();
q.pop();
if (s == target) return dist[s];
for (int i = 0; i < 4; i++) {
for (int step : {1, -1}) {
string t = s;
t[i] = '0' + (s[i] - '0' + step + 10) % 10;
if (!dead.count(t) && !dist.count(t)) {
dist[t] = dist[s] + 1;
q.push(t);
}
}
}
}
return -1;
}
vector<string> ladder(const string& begin, const string& end, const vector<string>& list) { // a state is a word
unordered_set<string> words(list.begin(), list.end());
unordered_map<string, string> parent = {{begin, ""}};
queue<string> q;
q.push(begin);
while (!q.empty()) {
string w = q.front();
q.pop();
if (w == end) {
vector<string> path;
for (string x = w; !x.empty(); x = parent[x]) path.insert(path.begin(), x);
return path;
}
for (size_t i = 0; i < w.size(); i++) {
for (char ch = 'a'; ch <= 'z'; ch++) {
string t = w;
t[i] = ch;
if (words.count(t) && !parent.count(t)) {
parent[t] = w;
q.push(t);
}
}
}
}
return {};
}
int main() {
cout << "turns from 0000 to 2020: " << openLock({"1000", "0010", "9000", "0090"}, "2020") << "\n";
auto path = ladder("cold", "warm", {"bold", "cord", "card", "ward", "warm", "worm", "word", "wore", "core", "corm"});
cout << "cold to warm: " << path.size() << " words:";
for (auto& w : path) cout << " " << w;
cout << "\n";
}
// turns from 0000 to 2020: 6
// cold to warm: 5 words: cold cord word ward warmfunction openLock(deadends, target) { // a state is the four digits; a move turns one wheel up or down
const dead = new Set(deadends);
if (dead.has("0000")) return -1;
const dist = new Map([["0000", 0]]);
const queue = ["0000"];
for (let head = 0; head < queue.length; head++) {
const s = queue[head];
if (s === target) return dist.get(s);
for (let i = 0; i < 4; i++) {
for (const step of [1, -1]) {
const t = s.slice(0, i) + String((Number(s[i]) + step + 10) % 10) + s.slice(i + 1);
if (!dead.has(t) && !dist.has(t)) {
dist.set(t, dist.get(s) + 1);
queue.push(t);
}
}
}
}
return -1;
}
function ladder(begin, end, list) { // a state is a word; a move changes one letter into another word
const words = new Set(list);
const parent = new Map([[begin, null]]);
const queue = [begin];
for (let head = 0; head < queue.length; head++) {
const w = queue[head];
if (w === end) {
const path = [];
for (let x = w; x !== null; x = parent.get(x)) path.unshift(x);
return path;
}
for (let i = 0; i < w.length; i++) {
for (const ch of "abcdefghijklmnopqrstuvwxyz") {
const t = w.slice(0, i) + ch + w.slice(i + 1);
if (words.has(t) && !parent.has(t)) {
parent.set(t, w);
queue.push(t);
}
}
}
}
return [];
}
console.log(`turns from 0000 to 2020: ${openLock(["1000", "0010", "9000", "0090"], "2020")}`);
const path = ladder("cold", "warm", ["bold", "cord", "card", "ward", "warm", "worm", "word", "wore", "core", "corm"]);
console.log(`cold to warm: ${path.length} words: ${path.join(" ")}`);
// turns from 0000 to 2020: 6
// cold to warm: 5 words: cold cord word ward warmfunction openLock(deadends: string[], target: string): number { // a state is the four digits; a move turns a wheel
const dead = new Set(deadends);
if (dead.has("0000")) return -1;
const dist = new Map<string, number>([["0000", 0]]);
const queue: string[] = ["0000"];
for (let head = 0; head < queue.length; head++) {
const s = queue[head];
if (s === target) return dist.get(s)!;
for (let i = 0; i < 4; i++) {
for (const step of [1, -1]) {
const t = s.slice(0, i) + String((Number(s[i]) + step + 10) % 10) + s.slice(i + 1);
if (!dead.has(t) && !dist.has(t)) {
dist.set(t, dist.get(s)! + 1);
queue.push(t);
}
}
}
}
return -1;
}
function ladder(begin: string, end: string, list: string[]): string[] { // a state is a word; a move changes a letter
const words = new Set(list);
const parent = new Map<string, string | null>([[begin, null]]);
const queue: string[] = [begin];
for (let head = 0; head < queue.length; head++) {
const w = queue[head];
if (w === end) {
const path: string[] = [];
for (let x: string | null = w; x !== null; x = parent.get(x) ?? null) path.unshift(x);
return path;
}
for (let i = 0; i < w.length; i++) {
for (const ch of "abcdefghijklmnopqrstuvwxyz") {
const t = w.slice(0, i) + ch + w.slice(i + 1);
if (words.has(t) && !parent.has(t)) {
parent.set(t, w);
queue.push(t);
}
}
}
}
return [];
}
console.log(`turns from 0000 to 2020: ${openLock(["1000", "0010", "9000", "0090"], "2020")}`);
const path = ladder("cold", "warm", ["bold", "cord", "card", "ward", "warm", "worm", "word", "wore", "core", "corm"]);
console.log(`cold to warm: ${path.length} words: ${path.join(" ")}`);
// turns from 0000 to 2020: 6
// cold to warm: 5 words: cold cord word ward warmusing System;
using System.Collections.Generic;
class Program {
static int OpenLock(string[] deadends, string target) { // a state is the four digits; a move turns one wheel
var dead = new HashSet<string>(deadends);
if (dead.Contains("0000")) return -1;
var dist = new Dictionary<string, int> { ["0000"] = 0 };
var queue = new Queue<string>();
queue.Enqueue("0000");
while (queue.Count > 0) {
string s = queue.Dequeue();
if (s == target) return dist[s];
for (int i = 0; i < 4; i++) {
foreach (int step in new[] {1, -1}) {
char[] t = s.ToCharArray();
t[i] = (char) ('0' + (t[i] - '0' + step + 10) % 10);
string next = new string(t);
if (!dead.Contains(next) && !dist.ContainsKey(next)) {
dist[next] = dist[s] + 1;
queue.Enqueue(next);
}
}
}
}
return -1;
}
static List<string> Ladder(string begin, string end, string[] list) { // a state is a word; a move changes a letter
var words = new HashSet<string>(list);
var parent = new Dictionary<string, string> { [begin] = null };
var queue = new Queue<string>();
queue.Enqueue(begin);
while (queue.Count > 0) {
string w = queue.Dequeue();
if (w == end) {
var path = new List<string>();
for (string x = w; x != null; x = parent[x]) path.Insert(0, x);
return path;
}
for (int i = 0; i < w.Length; i++) {
for (char ch = 'a'; ch <= 'z'; ch++) {
string t = w.Substring(0, i) + ch + w.Substring(i + 1);
if (words.Contains(t) && !parent.ContainsKey(t)) {
parent[t] = w;
queue.Enqueue(t);
}
}
}
}
return new List<string>();
}
static void Main() {
Console.WriteLine($"turns from 0000 to 2020: {OpenLock(new[] {"1000", "0010", "9000", "0090"}, "2020")}");
var path = Ladder("cold", "warm", new[] {"bold", "cord", "card", "ward", "warm", "worm", "word", "wore", "core", "corm"});
Console.WriteLine($"cold to warm: {path.Count} words: {string.Join(" ", path)}");
}
}
// turns from 0000 to 2020: 6
// cold to warm: 5 words: cold cord word ward warmpackage main
import (
"fmt"
"strings"
)
func openLock(deadends []string, target string) int { // a state is the four digits; a move turns one wheel
dead := map[string]bool{}
for _, d := range deadends {
dead[d] = true
}
if dead["0000"] {
return -1
}
dist := map[string]int{"0000": 0}
queue := []string{"0000"}
for head := 0; head < len(queue); head++ {
s := queue[head]
if s == target {
return dist[s]
}
for i := 0; i < 4; i++ {
for _, step := range []int{1, -1} {
t := []byte(s)
t[i] = byte('0' + (int(s[i]-'0')+step+10)%10)
next := string(t)
if _, seen := dist[next]; !dead[next] && !seen {
dist[next] = dist[s] + 1
queue = append(queue, next)
}
}
}
}
return -1
}
func ladder(begin, end string, list []string) []string { // a state is a word; a move changes one letter
words := map[string]bool{}
for _, w := range list {
words[w] = true
}
parent := map[string]string{begin: ""}
queue := []string{begin}
for head := 0; head < len(queue); head++ {
w := queue[head]
if w == end {
path := []string{}
for x := w; x != ""; x = parent[x] {
path = append([]string{x}, path...)
}
return path
}
for i := 0; i < len(w); i++ {
for ch := byte('a'); ch <= 'z'; ch++ {
t := w[:i] + string(ch) + w[i+1:]
if _, seen := parent[t]; words[t] && !seen {
parent[t] = w
queue = append(queue, t)
}
}
}
}
return []string{}
}
func main() {
fmt.Println("turns from 0000 to 2020:", openLock([]string{"1000", "0010", "9000", "0090"}, "2020"))
path := ladder("cold", "warm", []string{"bold", "cord", "card", "ward", "warm", "worm", "word", "wore", "core", "corm"})
fmt.Printf("cold to warm: %d words: %s\n", len(path), strings.Join(path, " "))
}
// turns from 0000 to 2020: 6
// cold to warm: 5 words: cold cord word ward warm6 turns, where the target needs only 4, two on the first wheel and two on the third: every first turn of those two wheels from 0000 lands on a dead end (1000, 9000, 0010 or 0090). So the search turns another wheel away and back, 2 turns more. The ladder is 5 words long: cold, cord, word, ward, warm. Word Ladder counts words, not changes, so 5 is the answer, and 0 when there's no way at all. To find a word's neighbours, change each letter to each of the 26 and look the result up in a set: 26 × L tries for a word of L letters, however long the list is, where comparing the word with every other word costs the whole list each time.
Word Ladder II wants every shortest ladder, not one. Search layer by layer and, for each word, keep every word in the layer before that reaches it; then read all the ladders back from the end. Minimum Steps via Multiply & Mod is the same search over numbers: a state is a value below 100,000, and a step multiplies it by one of the array's numbers.
A cell and what's left
Shortest Path in a Grid with Obstacles Elimination lets you walk through at most k walls, breaking each as you step onto it. Now a cell isn't enough to say where you are: standing on a cell with a break still in hand is better than standing there with none, because more cells are open to you next. So the state is (row, column, breaks left), and the mark goes on the state, not the cell. A grid of R × C cells has R × C × (k + 1) states, and BFS over them is the whole solution:
from collections import deque
grid = [".##...", # '#' is a wall: a step onto one breaks it, at most k in all
"..##..",
"#.#...",
"#...#."]
R, C = len(grid), len(grid[0])
def fewest_steps(k, mark_left=True): # a state is (row, column, breaks left)
seen = [[[False] * (k + 1) for _ in range(C)] for _ in range(R)]
seen[0][0][k if mark_left else 0] = True
queue = deque([(0, 0, k, 0)])
while queue:
r, c, left, steps = queue.popleft()
if (r, c) == (R - 1, C - 1):
return steps
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C:
now = left - (grid[nr][nc] == "#")
mark = now if mark_left else 0 # marking the cell alone: every breaks-left shares one mark
if now >= 0 and not seen[nr][nc][mark]:
seen[nr][nc][mark] = True
queue.append((nr, nc, now, steps + 1))
return -1
for k in range(3):
print(f"break at most {k}: {fewest_steps(k)} steps")
print(f"break at most 1, marking the cell alone: {fewest_steps(1, mark_left=False)} steps")
# break at most 0: 10 steps
# break at most 1: 8 steps
# break at most 2: 8 steps
# break at most 1, marking the cell alone: 10 stepsimport java.util.*;
public class Main {
static final String[] GRID = {".##...", // '#' is a wall: a step onto one breaks it, at most k in all
"..##..",
"#.#...",
"#...#."};
static final int R = GRID.length, C = GRID[0].length();
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int fewestSteps(int k, boolean markLeft) { // a state is (row, column, breaks left)
boolean[][][] seen = new boolean[R][C][k + 1];
seen[0][0][markLeft ? k : 0] = true;
ArrayDeque<int[]> queue = new ArrayDeque<>();
queue.add(new int[] {0, 0, k, 0});
while (!queue.isEmpty()) {
int[] s = queue.poll();
if (s[0] == R - 1 && s[1] == C - 1) return s[3];
for (int[] d : DIRS) {
int nr = s[0] + d[0], nc = s[1] + d[1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
int now = s[2] - (GRID[nr].charAt(nc) == '#' ? 1 : 0);
int mark = markLeft ? now : 0; // marking the cell alone: every breaks-left shares one mark
if (now >= 0 && !seen[nr][nc][mark]) {
seen[nr][nc][mark] = true;
queue.add(new int[] {nr, nc, now, s[3] + 1});
}
}
}
return -1;
}
public static void main(String[] args) {
for (int k = 0; k <= 2; k++) System.out.println("break at most " + k + ": " + fewestSteps(k, true) + " steps");
System.out.println("break at most 1, marking the cell alone: " + fewestSteps(1, false) + " steps");
}
}
// break at most 0: 10 steps
// break at most 1: 8 steps
// break at most 2: 8 steps
// break at most 1, marking the cell alone: 10 steps#include <bits/stdc++.h>
using namespace std;
const vector<string> GRID = {".##...", // '#' is a wall: a step onto one breaks it, at most k in all
"..##..",
"#.#...",
"#...#."};
const int R = GRID.size(), C = GRID[0].size();
const int DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int fewestSteps(int k, bool markLeft) { // a state is (row, column, breaks left)
vector<vector<vector<bool>>> seen(R, vector<vector<bool>>(C, vector<bool>(k + 1, false)));
seen[0][0][markLeft ? k : 0] = true;
queue<array<int, 4>> q;
q.push({0, 0, k, 0});
while (!q.empty()) {
auto [r, c, left, steps] = q.front();
q.pop();
if (r == R - 1 && c == C - 1) return steps;
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
int now = left - (GRID[nr][nc] == '#');
int mark = markLeft ? now : 0; // marking the cell alone: every breaks-left shares one mark
if (now >= 0 && !seen[nr][nc][mark]) {
seen[nr][nc][mark] = true;
q.push({nr, nc, now, steps + 1});
}
}
}
return -1;
}
int main() {
for (int k = 0; k <= 2; k++) cout << "break at most " << k << ": " << fewestSteps(k, true) << " steps\n";
cout << "break at most 1, marking the cell alone: " << fewestSteps(1, false) << " steps\n";
}
// break at most 0: 10 steps
// break at most 1: 8 steps
// break at most 2: 8 steps
// break at most 1, marking the cell alone: 10 stepsconst grid = [".##...", // '#' is a wall: a step onto one breaks it, at most k in all
"..##..",
"#.#...",
"#...#."];
const R = grid.length, C = grid[0].length;
function fewestSteps(k, markLeft = true) { // a state is (row, column, breaks left)
const seen = Array.from({ length: R }, () => Array.from({ length: C }, () => new Array(k + 1).fill(false)));
seen[0][0][markLeft ? k : 0] = true;
const queue = [[0, 0, k, 0]];
for (let head = 0; head < queue.length; head++) {
const [r, c, left, steps] = queue[head];
if (r === R - 1 && c === C - 1) return steps;
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
const now = left - (grid[nr][nc] === "#" ? 1 : 0);
const mark = markLeft ? now : 0; // marking the cell alone: every breaks-left shares one mark
if (now >= 0 && !seen[nr][nc][mark]) {
seen[nr][nc][mark] = true;
queue.push([nr, nc, now, steps + 1]);
}
}
}
return -1;
}
for (let k = 0; k <= 2; k++) console.log(`break at most ${k}: ${fewestSteps(k)} steps`);
console.log(`break at most 1, marking the cell alone: ${fewestSteps(1, false)} steps`);
// break at most 0: 10 steps
// break at most 1: 8 steps
// break at most 2: 8 steps
// break at most 1, marking the cell alone: 10 stepsconst grid: string[] = [".##...", // '#' is a wall: a step onto one breaks it, at most k in all
"..##..",
"#.#...",
"#...#."];
const R = grid.length, C = grid[0].length;
function fewestSteps(k: number, markLeft = true): number { // a state is (row, column, breaks left)
const seen: boolean[][][] = Array.from({ length: R }, () =>
Array.from({ length: C }, () => new Array<boolean>(k + 1).fill(false)));
seen[0][0][markLeft ? k : 0] = true;
const queue: [number, number, number, number][] = [[0, 0, k, 0]];
for (let head = 0; head < queue.length; head++) {
const [r, c, left, steps] = queue[head];
if (r === R - 1 && c === C - 1) return steps;
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
const now = left - (grid[nr][nc] === "#" ? 1 : 0);
const mark = markLeft ? now : 0; // marking the cell alone: every breaks-left shares one mark
if (now >= 0 && !seen[nr][nc][mark]) {
seen[nr][nc][mark] = true;
queue.push([nr, nc, now, steps + 1]);
}
}
}
return -1;
}
for (let k = 0; k <= 2; k++) console.log(`break at most ${k}: ${fewestSteps(k)} steps`);
console.log(`break at most 1, marking the cell alone: ${fewestSteps(1, false)} steps`);
// break at most 0: 10 steps
// break at most 1: 8 steps
// break at most 2: 8 steps
// break at most 1, marking the cell alone: 10 stepsusing System;
using System.Collections.Generic;
class Program {
static readonly string[] Grid = { ".##...", // '#' is a wall: a step onto one breaks it, at most k in all
"..##..",
"#.#...",
"#...#." };
static readonly int R = Grid.Length, C = Grid[0].Length;
static readonly int[][] Dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
static int FewestSteps(int k, bool markLeft = true) { // a state is (row, column, breaks left)
var seen = new bool[R, C, k + 1];
seen[0, 0, markLeft ? k : 0] = true;
var queue = new Queue<(int r, int c, int left, int steps)>();
queue.Enqueue((0, 0, k, 0));
while (queue.Count > 0) {
var (r, c, left, steps) = queue.Dequeue();
if (r == R - 1 && c == C - 1) return steps;
foreach (int[] d in Dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
int now = left - (Grid[nr][nc] == '#' ? 1 : 0);
int mark = markLeft ? now : 0; // marking the cell alone: every breaks-left shares one mark
if (now >= 0 && !seen[nr, nc, mark]) {
seen[nr, nc, mark] = true;
queue.Enqueue((nr, nc, now, steps + 1));
}
}
}
return -1;
}
static void Main() {
for (int k = 0; k <= 2; k++) Console.WriteLine($"break at most {k}: {FewestSteps(k)} steps");
Console.WriteLine($"break at most 1, marking the cell alone: {FewestSteps(1, false)} steps");
}
}
// break at most 0: 10 steps
// break at most 1: 8 steps
// break at most 2: 8 steps
// break at most 1, marking the cell alone: 10 stepspackage main
import "fmt"
var grid = []string{ // '#' is a wall: a step onto one breaks it, at most k in all
".##...",
"..##..",
"#.#...",
"#...#.",
}
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func fewestSteps(k int, markLeft bool) int { // a state is (row, column, breaks left)
R, C := len(grid), len(grid[0])
seen := make([][][]bool, R)
for r := range seen {
seen[r] = make([][]bool, C)
for c := range seen[r] {
seen[r][c] = make([]bool, k+1)
}
}
if markLeft {
seen[0][0][k] = true
} else {
seen[0][0][0] = true
}
queue := [][4]int{{0, 0, k, 0}}
for head := 0; head < len(queue); head++ {
r, c, left, steps := queue[head][0], queue[head][1], queue[head][2], queue[head][3]
if r == R-1 && c == C-1 {
return steps
}
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= R || nc < 0 || nc >= C {
continue
}
now := left
if grid[nr][nc] == '#' {
now--
}
mark := 0 // marking the cell alone: every breaks-left shares one mark
if markLeft {
mark = now
}
if now >= 0 && !seen[nr][nc][mark] {
seen[nr][nc][mark] = true
queue = append(queue, [4]int{nr, nc, now, steps + 1})
}
}
}
return -1
}
func main() {
for k := 0; k <= 2; k++ {
fmt.Printf("break at most %d: %d steps\n", k, fewestSteps(k, true))
}
fmt.Printf("break at most 1, marking the cell alone: %d steps\n", fewestSteps(1, false))
}
// break at most 0: 10 steps
// break at most 1: 8 steps
// break at most 2: 8 steps
// break at most 1, marking the cell alone: 10 stepsWith no breaks the way round takes 10 steps. One break cuts it to 8, as short as any route between the two corners can be, so a second break changes nothing. The last line is the same search with the mark on the cell alone: 10 steps, though a break was allowed. On its way down it broke the wall at (2,0), which saves nothing, and from there reached (2,1) on the same step as the path that still had its break, but first in the queue. It marked (2,1), the other path was turned away, and every cell after that was reached with no break left, so the wall at (3,4), the one worth breaking, stayed shut.
Steps that cost 0 or 1
Minimum Obstacle Removal to Reach Corner asks for the fewest obstacles to remove on the way from the top left to the bottom right: a step onto a free cell costs 0, a step onto an obstacle costs 1. A plain BFS counts steps, not obstacles, so keeping each cell's first arrival can keep the wrong cost. With costs of only 0 and 1, a deque, a queue you can add to at either end, puts it right: a cell reached for free goes on the front, with the cells it's as cheap as, and a cell reached through an obstacle goes on the back. A cell can be reached again more cheaply later, so each keeps the lowest cost seen and goes in again when that improves:
from collections import deque
grid = [[0, 1, 0, 0], # 1 is an obstacle: stepping onto one removes it, at a cost of 1
[1, 1, 0, 1],
[0, 0, 1, 0],
[0, 1, 1, 0]]
R, C = len(grid), len(grid[0])
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
def first_arrival(): # a plain queue: a cell keeps the cost it was first reached with
cost = [[-1] * C for _ in range(R)]
cost[0][0] = 0
queue = deque([(0, 0)])
while queue:
r, c = queue.popleft()
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and cost[nr][nc] == -1:
cost[nr][nc] = cost[r][c] + grid[nr][nc]
queue.append((nr, nc))
return cost
def zero_one(order): # a deque: a free step goes on the front, an obstacle on the back
cost = [[float("inf")] * C for _ in range(R)]
cost[0][0] = 0
dq = deque([(0, 0)])
while dq:
r, c = dq.popleft()
order.append(cost[r][c])
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and cost[r][c] + grid[nr][nc] < cost[nr][nc]:
cost[nr][nc] = cost[r][c] + grid[nr][nc] # cheaper than before: it can go in again
if grid[nr][nc] == 0:
dq.appendleft((nr, nc)) # as cheap as where it came from: it goes first
else:
dq.append((nr, nc)) # one more: it waits behind this cost
return cost
def show(title, cost):
print(title)
for row in cost:
print(" ".join(map(str, row)))
show("a plain queue, first arrival kept:", first_arrival())
order = []
show("the deque, free steps to the front:", zero_one(order))
print("costs in the order cells came off:", " ".join(map(str, order)))
# a plain queue, first arrival kept:
# 0 1 1 1
# 1 2 2 3
# 1 1 2 2
# 1 2 3 3
# the deque, free steps to the front:
# 0 1 1 1
# 1 2 1 2
# 1 1 2 2
# 1 2 3 2
# costs in the order cells came off: 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3import java.util.*;
public class Main {
static final int[][] GRID = {{0, 1, 0, 0}, // 1 is an obstacle: stepping onto one removes it, at a cost of 1
{1, 1, 0, 1},
{0, 0, 1, 0},
{0, 1, 1, 0}};
static final int R = GRID.length, C = GRID[0].length;
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int[][] firstArrival() { // a plain queue: a cell keeps the cost it was first reached with
int[][] cost = new int[R][C];
for (int[] row : cost) Arrays.fill(row, -1);
cost[0][0] = 0;
ArrayDeque<int[]> queue = new ArrayDeque<>();
queue.add(new int[] {0, 0});
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int[] d : DIRS) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && cost[nr][nc] == -1) {
cost[nr][nc] = cost[cur[0]][cur[1]] + GRID[nr][nc];
queue.add(new int[] {nr, nc});
}
}
}
return cost;
}
static int[][] zeroOne(List<Integer> order) { // a deque: a free step goes on the front, an obstacle on the back
int[][] cost = new int[R][C];
for (int[] row : cost) Arrays.fill(row, Integer.MAX_VALUE);
cost[0][0] = 0;
ArrayDeque<int[]> dq = new ArrayDeque<>();
dq.add(new int[] {0, 0});
while (!dq.isEmpty()) {
int[] cur = dq.pollFirst();
int here = cost[cur[0]][cur[1]];
order.add(here);
for (int[] d : DIRS) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && here + GRID[nr][nc] < cost[nr][nc]) {
cost[nr][nc] = here + GRID[nr][nc]; // cheaper than before: it can go in again
if (GRID[nr][nc] == 0) dq.addFirst(new int[] {nr, nc}); // as cheap as where it came from: first
else dq.addLast(new int[] {nr, nc}); // one more: it waits behind this cost
}
}
}
return cost;
}
static void show(String title, int[][] cost) {
System.out.println(title);
for (int[] row : cost) {
StringJoiner s = new StringJoiner(" ");
for (int v : row) s.add(String.valueOf(v));
System.out.println(s);
}
}
public static void main(String[] args) {
show("a plain queue, first arrival kept:", firstArrival());
List<Integer> order = new ArrayList<>();
show("the deque, free steps to the front:", zeroOne(order));
StringJoiner s = new StringJoiner(" ");
for (int v : order) s.add(String.valueOf(v));
System.out.println("costs in the order cells came off: " + s);
}
}
// a plain queue, first arrival kept:
// 0 1 1 1
// 1 2 2 3
// 1 1 2 2
// 1 2 3 3
// the deque, free steps to the front:
// 0 1 1 1
// 1 2 1 2
// 1 1 2 2
// 1 2 3 2
// costs in the order cells came off: 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3#include <bits/stdc++.h>
using namespace std;
const vector<vector<int>> GRID = {{0, 1, 0, 0}, // 1 is an obstacle: stepping onto one removes it, cost 1
{1, 1, 0, 1},
{0, 0, 1, 0},
{0, 1, 1, 0}};
const int R = GRID.size(), C = GRID[0].size();
const int DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<int>> firstArrival() { // a plain queue: a cell keeps the cost it was first reached with
vector<vector<int>> cost(R, vector<int>(C, -1));
cost[0][0] = 0;
queue<pair<int, int>> q;
q.push({0, 0});
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && cost[nr][nc] == -1) {
cost[nr][nc] = cost[r][c] + GRID[nr][nc];
q.push({nr, nc});
}
}
}
return cost;
}
vector<vector<int>> zeroOne(vector<int>& order) { // a deque: a free step goes on the front, an obstacle on the back
vector<vector<int>> cost(R, vector<int>(C, INT_MAX));
cost[0][0] = 0;
deque<pair<int, int>> dq = {{0, 0}};
while (!dq.empty()) {
auto [r, c] = dq.front();
dq.pop_front();
order.push_back(cost[r][c]);
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && cost[r][c] + GRID[nr][nc] < cost[nr][nc]) {
cost[nr][nc] = cost[r][c] + GRID[nr][nc]; // cheaper than before: it can go in again
if (GRID[nr][nc] == 0) dq.push_front({nr, nc}); // as cheap as where it came from: it goes first
else dq.push_back({nr, nc}); // one more: it waits behind this cost
}
}
}
return cost;
}
void show(const string& title, const vector<vector<int>>& cost) {
cout << title << "\n";
for (auto& row : cost) {
for (size_t c = 0; c < row.size(); c++) cout << (c ? " " : "") << row[c];
cout << "\n";
}
}
int main() {
show("a plain queue, first arrival kept:", firstArrival());
vector<int> order;
show("the deque, free steps to the front:", zeroOne(order));
cout << "costs in the order cells came off:";
for (int v : order) cout << " " << v;
cout << "\n";
}
// a plain queue, first arrival kept:
// 0 1 1 1
// 1 2 2 3
// 1 1 2 2
// 1 2 3 3
// the deque, free steps to the front:
// 0 1 1 1
// 1 2 1 2
// 1 1 2 2
// 1 2 3 2
// costs in the order cells came off: 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3const grid = [[0, 1, 0, 0], // 1 is an obstacle: stepping onto one removes it, at a cost of 1
[1, 1, 0, 1],
[0, 0, 1, 0],
[0, 1, 1, 0]];
const R = grid.length, C = grid[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function firstArrival() { // a plain queue: a cell keeps the cost it was first reached with
const cost = Array.from({ length: R }, () => new Array(C).fill(-1));
cost[0][0] = 0;
const queue = [[0, 0]];
for (let head = 0; head < queue.length; head++) {
const [r, c] = queue[head];
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && cost[nr][nc] === -1) {
cost[nr][nc] = cost[r][c] + grid[nr][nc];
queue.push([nr, nc]);
}
}
}
return cost;
}
function zeroOne(order) { // a deque: a free step goes on the front, an obstacle on the back
const cost = Array.from({ length: R }, () => new Array(C).fill(Infinity));
cost[0][0] = 0;
const dq = [[0, 0]]; // no deque built in: unshift adds at the front, push at the back
while (dq.length) {
const [r, c] = dq.shift();
order.push(cost[r][c]);
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && cost[r][c] + grid[nr][nc] < cost[nr][nc]) {
cost[nr][nc] = cost[r][c] + grid[nr][nc]; // cheaper than before: it can go in again
if (grid[nr][nc] === 0) dq.unshift([nr, nc]); // as cheap as where it came from: it goes first
else dq.push([nr, nc]); // one more: it waits behind this cost
}
}
}
return cost;
}
function show(title, cost) {
console.log(title);
for (const row of cost) console.log(row.join(" "));
}
show("a plain queue, first arrival kept:", firstArrival());
const order = [];
show("the deque, free steps to the front:", zeroOne(order));
console.log(`costs in the order cells came off: ${order.join(" ")}`);
// a plain queue, first arrival kept:
// 0 1 1 1
// 1 2 2 3
// 1 1 2 2
// 1 2 3 3
// the deque, free steps to the front:
// 0 1 1 1
// 1 2 1 2
// 1 1 2 2
// 1 2 3 2
// costs in the order cells came off: 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3const grid: number[][] = [[0, 1, 0, 0], // 1 is an obstacle: stepping onto one removes it, at a cost of 1
[1, 1, 0, 1],
[0, 0, 1, 0],
[0, 1, 1, 0]];
const R = grid.length, C = grid[0].length;
const DIRS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function firstArrival(): number[][] { // a plain queue: a cell keeps the cost it was first reached with
const cost: number[][] = Array.from({ length: R }, () => new Array(C).fill(-1));
cost[0][0] = 0;
const queue: [number, number][] = [[0, 0]];
for (let head = 0; head < queue.length; head++) {
const [r, c] = queue[head];
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && cost[nr][nc] === -1) {
cost[nr][nc] = cost[r][c] + grid[nr][nc];
queue.push([nr, nc]);
}
}
}
return cost;
}
function zeroOne(order: number[]): number[][] { // a deque: a free step goes on the front, an obstacle on the back
const cost: number[][] = Array.from({ length: R }, () => new Array(C).fill(Infinity));
cost[0][0] = 0;
const dq: [number, number][] = [[0, 0]]; // no deque built in: unshift adds at the front, push at the back
while (dq.length) {
const [r, c] = dq.shift()!;
order.push(cost[r][c]);
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && cost[r][c] + grid[nr][nc] < cost[nr][nc]) {
cost[nr][nc] = cost[r][c] + grid[nr][nc]; // cheaper than before: it can go in again
if (grid[nr][nc] === 0) dq.unshift([nr, nc]); // as cheap as where it came from: it goes first
else dq.push([nr, nc]); // one more: it waits behind this cost
}
}
}
return cost;
}
function show(title: string, cost: number[][]): void {
console.log(title);
for (const row of cost) console.log(row.join(" "));
}
show("a plain queue, first arrival kept:", firstArrival());
const order: number[] = [];
show("the deque, free steps to the front:", zeroOne(order));
console.log(`costs in the order cells came off: ${order.join(" ")}`);
// a plain queue, first arrival kept:
// 0 1 1 1
// 1 2 2 3
// 1 1 2 2
// 1 2 3 3
// the deque, free steps to the front:
// 0 1 1 1
// 1 2 1 2
// 1 1 2 2
// 1 2 3 2
// costs in the order cells came off: 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3using System;
using System.Collections.Generic;
class Program {
static readonly int[,] Grid = { {0, 1, 0, 0}, // 1 is an obstacle: stepping onto one removes it, at a cost of 1
{1, 1, 0, 1},
{0, 0, 1, 0},
{0, 1, 1, 0} };
static readonly int R = Grid.GetLength(0), C = Grid.GetLength(1);
static readonly int[][] Dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
static int[,] FirstArrival() { // a plain queue: a cell keeps the cost it was first reached with
var cost = new int[R, C];
for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) cost[r, c] = -1;
cost[0, 0] = 0;
var queue = new Queue<(int r, int c)>();
queue.Enqueue((0, 0));
while (queue.Count > 0) {
var (r, c) = queue.Dequeue();
foreach (int[] d in Dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && cost[nr, nc] == -1) {
cost[nr, nc] = cost[r, c] + Grid[nr, nc];
queue.Enqueue((nr, nc));
}
}
}
return cost;
}
static int[,] ZeroOne(List<int> order) { // a deque: a free step goes on the front, an obstacle on the back
var cost = new int[R, C];
for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) cost[r, c] = int.MaxValue;
cost[0, 0] = 0;
var dq = new LinkedList<(int r, int c)>(); // AddFirst puts a cell on the front, AddLast on the back
dq.AddLast((0, 0));
while (dq.Count > 0) {
var (r, c) = dq.First.Value;
dq.RemoveFirst();
order.Add(cost[r, c]);
foreach (int[] d in Dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && cost[r, c] + Grid[nr, nc] < cost[nr, nc]) {
cost[nr, nc] = cost[r, c] + Grid[nr, nc]; // cheaper than before: it can go in again
if (Grid[nr, nc] == 0) dq.AddFirst((nr, nc)); // as cheap as where it came from: it goes first
else dq.AddLast((nr, nc)); // one more: it waits behind this cost
}
}
}
return cost;
}
static void Show(string title, int[,] cost) {
Console.WriteLine(title);
for (int r = 0; r < R; r++) {
var row = new List<int>();
for (int c = 0; c < C; c++) row.Add(cost[r, c]);
Console.WriteLine(string.Join(" ", row));
}
}
static void Main() {
Show("a plain queue, first arrival kept:", FirstArrival());
var order = new List<int>();
Show("the deque, free steps to the front:", ZeroOne(order));
Console.WriteLine($"costs in the order cells came off: {string.Join(" ", order)}");
}
}
// a plain queue, first arrival kept:
// 0 1 1 1
// 1 2 2 3
// 1 1 2 2
// 1 2 3 3
// the deque, free steps to the front:
// 0 1 1 1
// 1 2 1 2
// 1 1 2 2
// 1 2 3 2
// costs in the order cells came off: 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3package main
import (
"container/list"
"fmt"
"math"
"strconv"
"strings"
)
var grid = [][]int{ // 1 is an obstacle: stepping onto one removes it, at a cost of 1
{0, 1, 0, 0},
{1, 1, 0, 1},
{0, 0, 1, 0},
{0, 1, 1, 0},
}
var R, C = len(grid), len(grid[0])
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func filled(v int) [][]int {
cost := make([][]int, R)
for r := range cost {
cost[r] = make([]int, C)
for c := range cost[r] {
cost[r][c] = v
}
}
return cost
}
func firstArrival() [][]int { // a plain queue: a cell keeps the cost it was first reached with
cost := filled(-1)
cost[0][0] = 0
queue := [][2]int{{0, 0}}
for head := 0; head < len(queue); head++ {
r, c := queue[head][0], queue[head][1]
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < R && nc >= 0 && nc < C && cost[nr][nc] == -1 {
cost[nr][nc] = cost[r][c] + grid[nr][nc]
queue = append(queue, [2]int{nr, nc})
}
}
}
return cost
}
func zeroOne(order *[]int) [][]int { // a deque: a free step goes on the front, an obstacle on the back
cost := filled(math.MaxInt32)
cost[0][0] = 0
dq := list.New() // PushFront puts a cell on the front, PushBack on the back
dq.PushBack([2]int{0, 0})
for dq.Len() > 0 {
cur := dq.Remove(dq.Front()).([2]int)
r, c := cur[0], cur[1]
*order = append(*order, cost[r][c])
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < R && nc >= 0 && nc < C && cost[r][c]+grid[nr][nc] < cost[nr][nc] {
cost[nr][nc] = cost[r][c] + grid[nr][nc] // cheaper than before: it can go in again
if grid[nr][nc] == 0 {
dq.PushFront([2]int{nr, nc}) // as cheap as where it came from: it goes first
} else {
dq.PushBack([2]int{nr, nc}) // one more: it waits behind this cost
}
}
}
}
return cost
}
func join(xs []int) string {
parts := make([]string, len(xs))
for i, x := range xs {
parts[i] = strconv.Itoa(x)
}
return strings.Join(parts, " ")
}
func show(title string, cost [][]int) {
fmt.Println(title)
for _, row := range cost {
fmt.Println(join(row))
}
}
func main() {
show("a plain queue, first arrival kept:", firstArrival())
order := []int{}
show("the deque, free steps to the front:", zeroOne(&order))
fmt.Println("costs in the order cells came off:", join(order))
}
// a plain queue, first arrival kept:
// 0 1 1 1
// 1 2 2 3
// 1 1 2 2
// 1 2 3 3
// the deque, free steps to the front:
// 0 1 1 1
// 1 2 1 2
// 1 1 2 2
// 1 2 3 2
// costs in the order cells came off: 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3The plain queue got 3 cells wrong, the corner among them: 3 obstacles where 2 will do. It reached (1,2) first from (1,1), which had cost 2 to get to, and turned away the way from (0,2), which had cost 1: both are 3 steps from the start, and a queue knows only steps. The deque's cells came off in order of cost, the 0, then the 1s, then the 2s, then the 3, never a cheaper cell after a dearer one. That's BFS's layers again, by cost instead of by steps, so a cell's cost is settled when it first comes off, and the whole search is O(R × C).
JavaScript and TypeScript have no deque built in: unshift and shift stand in here, but each moves the whole array, so on a big grid use a deque of your own. Costs other than 0 and 1 need Dijkstra's algorithm, in Weighted Shortest Paths: Dijkstra, Bellman-Ford and Floyd-Warshall.
Buses, not stops
Bus Routes asks for the fewest buses from one stop to another, given each bus's route. One bus can carry you past many stops for the price of one, so a step of the search is a bus, not a stop: the buses through the start are 1 bus away, the buses that share a stop with those are 2, and so on. Each bus is taken off the queue once and each stop's buses are looked at once, so the work is the total length of the routes, where joining every two stops on a route would cost the square of each route's length:
from collections import deque
def fewest_buses(routes, source, target): # the search runs over buses: one step is one more bus
if source == target:
return []
buses_at = {} # stop -> the buses that stop there
for b, route in enumerate(routes):
for stop in route:
buses_at.setdefault(stop, []).append(b)
parent = [-2] * len(routes) # -2: not reached yet, -1: a bus through the start
queue = deque()
for b in buses_at.get(source, []):
parent[b] = -1
queue.append(b)
stops_seen = {source}
while queue:
b = queue.popleft()
for stop in routes[b]:
if stop == target: # read the buses back from this one
taken = []
while b != -1:
taken.append(b)
b = parent[b]
return taken[::-1]
if stop in stops_seen: # each stop's buses are looked at once
continue
stops_seen.add(stop)
for nb in buses_at[stop]:
if parent[nb] == -2:
parent[nb] = b
queue.append(nb)
return None
routes = [[1, 4, 9], [9, 3], [3, 8, 2], [4, 7]]
for source, target in ((1, 8), (7, 1), (1, 5)):
taken = fewest_buses(routes, source, target)
if taken is None:
print(f"from {source} to {target}: -1")
else:
print(f"from {source} to {target}: {len(taken)} buses ({' '.join(map(str, taken))})")
# from 1 to 8: 3 buses (0 1 2)
# from 7 to 1: 2 buses (3 0)
# from 1 to 5: -1import java.util.*;
public class Main {
static List<Integer> fewestBuses(int[][] routes, int source, int target) { // one step is one more bus
if (source == target) return new ArrayList<>();
Map<Integer, List<Integer>> busesAt = new HashMap<>(); // stop -> the buses that stop there
for (int b = 0; b < routes.length; b++) {
for (int stop : routes[b]) busesAt.computeIfAbsent(stop, x -> new ArrayList<>()).add(b);
}
int[] parent = new int[routes.length];
Arrays.fill(parent, -2); // -2: not reached yet, -1: a bus through the start
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int b : busesAt.getOrDefault(source, new ArrayList<>())) {
parent[b] = -1;
queue.add(b);
}
Set<Integer> stopsSeen = new HashSet<>();
stopsSeen.add(source);
while (!queue.isEmpty()) {
int b = queue.poll();
for (int stop : routes[b]) {
if (stop == target) { // read the buses back from this one
LinkedList<Integer> taken = new LinkedList<>();
for (int x = b; x != -1; x = parent[x]) taken.addFirst(x);
return taken;
}
if (!stopsSeen.add(stop)) continue; // each stop's buses are looked at once
for (int nb : busesAt.get(stop)) {
if (parent[nb] == -2) {
parent[nb] = b;
queue.add(nb);
}
}
}
}
return null;
}
public static void main(String[] args) {
int[][] routes = {{1, 4, 9}, {9, 3}, {3, 8, 2}, {4, 7}};
int[][] trips = {{1, 8}, {7, 1}, {1, 5}};
for (int[] t : trips) {
List<Integer> taken = fewestBuses(routes, t[0], t[1]);
if (taken == null) {
System.out.println("from " + t[0] + " to " + t[1] + ": -1");
} else {
StringJoiner s = new StringJoiner(" ");
for (int b : taken) s.add(String.valueOf(b));
System.out.println("from " + t[0] + " to " + t[1] + ": " + taken.size() + " buses (" + s + ")");
}
}
}
}
// from 1 to 8: 3 buses (0 1 2)
// from 7 to 1: 2 buses (3 0)
// from 1 to 5: -1#include <bits/stdc++.h>
using namespace std;
optional<vector<int>> fewestBuses(const vector<vector<int>>& routes, int source, int target) { // a step: a bus
if (source == target) return vector<int>{};
unordered_map<int, vector<int>> busesAt; // stop -> the buses that stop there
for (int b = 0; b < (int) routes.size(); b++) {
for (int stop : routes[b]) busesAt[stop].push_back(b);
}
vector<int> parent(routes.size(), -2); // -2: not reached yet, -1: a bus through the start
queue<int> q;
for (int b : busesAt[source]) {
parent[b] = -1;
q.push(b);
}
unordered_set<int> stopsSeen = {source};
while (!q.empty()) {
int b = q.front();
q.pop();
for (int stop : routes[b]) {
if (stop == target) { // read the buses back from this one
vector<int> taken;
for (int x = b; x != -1; x = parent[x]) taken.insert(taken.begin(), x);
return taken;
}
if (!stopsSeen.insert(stop).second) continue; // each stop's buses are looked at once
for (int nb : busesAt[stop]) {
if (parent[nb] == -2) {
parent[nb] = b;
q.push(nb);
}
}
}
}
return nullopt;
}
int main() {
vector<vector<int>> routes = {{1, 4, 9}, {9, 3}, {3, 8, 2}, {4, 7}};
for (auto [source, target] : vector<pair<int, int>>{{1, 8}, {7, 1}, {1, 5}}) {
auto taken = fewestBuses(routes, source, target);
cout << "from " << source << " to " << target << ": ";
if (!taken) {
cout << "-1\n";
continue;
}
cout << taken->size() << " buses (";
for (size_t i = 0; i < taken->size(); i++) cout << (i ? " " : "") << (*taken)[i];
cout << ")\n";
}
}
// from 1 to 8: 3 buses (0 1 2)
// from 7 to 1: 2 buses (3 0)
// from 1 to 5: -1function fewestBuses(routes, source, target) { // the search runs over buses: one step is one more bus
if (source === target) return [];
const busesAt = new Map(); // stop -> the buses that stop there
routes.forEach((route, b) => {
for (const stop of route) {
if (!busesAt.has(stop)) busesAt.set(stop, []);
busesAt.get(stop).push(b);
}
});
const parent = new Array(routes.length).fill(-2); // -2: not reached yet, -1: a bus through the start
const queue = [];
for (const b of busesAt.get(source) ?? []) {
parent[b] = -1;
queue.push(b);
}
const stopsSeen = new Set([source]);
for (let head = 0; head < queue.length; head++) {
const b = queue[head];
for (const stop of routes[b]) {
if (stop === target) { // read the buses back from this one
const taken = [];
for (let x = b; x !== -1; x = parent[x]) taken.unshift(x);
return taken;
}
if (stopsSeen.has(stop)) continue; // each stop's buses are looked at once
stopsSeen.add(stop);
for (const nb of busesAt.get(stop)) {
if (parent[nb] === -2) {
parent[nb] = b;
queue.push(nb);
}
}
}
}
return null;
}
const routes = [[1, 4, 9], [9, 3], [3, 8, 2], [4, 7]];
for (const [source, target] of [[1, 8], [7, 1], [1, 5]]) {
const taken = fewestBuses(routes, source, target);
console.log(taken === null ? `from ${source} to ${target}: -1`
: `from ${source} to ${target}: ${taken.length} buses (${taken.join(" ")})`);
}
// from 1 to 8: 3 buses (0 1 2)
// from 7 to 1: 2 buses (3 0)
// from 1 to 5: -1function fewestBuses(routes: number[][], source: number, target: number): number[] | null { // a step: a bus
if (source === target) return [];
const busesAt = new Map<number, number[]>(); // stop -> the buses that stop there
routes.forEach((route, b) => {
for (const stop of route) {
if (!busesAt.has(stop)) busesAt.set(stop, []);
busesAt.get(stop)!.push(b);
}
});
const parent: number[] = new Array(routes.length).fill(-2); // -2: not reached yet, -1: a bus through the start
const queue: number[] = [];
for (const b of busesAt.get(source) ?? []) {
parent[b] = -1;
queue.push(b);
}
const stopsSeen = new Set<number>([source]);
for (let head = 0; head < queue.length; head++) {
const b = queue[head];
for (const stop of routes[b]) {
if (stop === target) { // read the buses back from this one
const taken: number[] = [];
for (let x = b; x !== -1; x = parent[x]) taken.unshift(x);
return taken;
}
if (stopsSeen.has(stop)) continue; // each stop's buses are looked at once
stopsSeen.add(stop);
for (const nb of busesAt.get(stop)!) {
if (parent[nb] === -2) {
parent[nb] = b;
queue.push(nb);
}
}
}
}
return null;
}
const routes: number[][] = [[1, 4, 9], [9, 3], [3, 8, 2], [4, 7]];
for (const [source, target] of [[1, 8], [7, 1], [1, 5]]) {
const taken = fewestBuses(routes, source, target);
console.log(taken === null ? `from ${source} to ${target}: -1`
: `from ${source} to ${target}: ${taken.length} buses (${taken.join(" ")})`);
}
// from 1 to 8: 3 buses (0 1 2)
// from 7 to 1: 2 buses (3 0)
// from 1 to 5: -1using System;
using System.Collections.Generic;
class Program {
static List<int> FewestBuses(int[][] routes, int source, int target) { // one step is one more bus
if (source == target) return new List<int>();
var busesAt = new Dictionary<int, List<int>>(); // stop -> the buses that stop there
for (int b = 0; b < routes.Length; b++) {
foreach (int stop in routes[b]) {
if (!busesAt.ContainsKey(stop)) busesAt[stop] = new List<int>();
busesAt[stop].Add(b);
}
}
var parent = new int[routes.Length];
Array.Fill(parent, -2); // -2: not reached yet, -1: a bus through the start
var queue = new Queue<int>();
if (busesAt.TryGetValue(source, out var first)) {
foreach (int b in first) {
parent[b] = -1;
queue.Enqueue(b);
}
}
var stopsSeen = new HashSet<int> { source };
while (queue.Count > 0) {
int b = queue.Dequeue();
foreach (int stop in routes[b]) {
if (stop == target) { // read the buses back from this one
var taken = new List<int>();
for (int x = b; x != -1; x = parent[x]) taken.Insert(0, x);
return taken;
}
if (!stopsSeen.Add(stop)) continue; // each stop's buses are looked at once
foreach (int nb in busesAt[stop]) {
if (parent[nb] == -2) {
parent[nb] = b;
queue.Enqueue(nb);
}
}
}
}
return null;
}
static void Main() {
int[][] routes = { new[] {1, 4, 9}, new[] {9, 3}, new[] {3, 8, 2}, new[] {4, 7} };
foreach (var (source, target) in new[] { (1, 8), (7, 1), (1, 5) }) {
var taken = FewestBuses(routes, source, target);
Console.WriteLine(taken == null ? $"from {source} to {target}: -1"
: $"from {source} to {target}: {taken.Count} buses ({string.Join(" ", taken)})");
}
}
}
// from 1 to 8: 3 buses (0 1 2)
// from 7 to 1: 2 buses (3 0)
// from 1 to 5: -1package main
import (
"fmt"
"strconv"
"strings"
)
func fewestBuses(routes [][]int, source, target int) ([]int, bool) { // one step is one more bus
if source == target {
return []int{}, true
}
busesAt := map[int][]int{} // stop -> the buses that stop there
for b, route := range routes {
for _, stop := range route {
busesAt[stop] = append(busesAt[stop], b)
}
}
parent := make([]int, len(routes))
for i := range parent {
parent[i] = -2 // -2: not reached yet, -1: a bus through the start
}
queue := []int{}
for _, b := range busesAt[source] {
parent[b] = -1
queue = append(queue, b)
}
stopsSeen := map[int]bool{source: true}
for head := 0; head < len(queue); head++ {
b := queue[head]
for _, stop := range routes[b] {
if stop == target { // read the buses back from this one
taken := []int{}
for x := b; x != -1; x = parent[x] {
taken = append([]int{x}, taken...)
}
return taken, true
}
if stopsSeen[stop] { // each stop's buses are looked at once
continue
}
stopsSeen[stop] = true
for _, nb := range busesAt[stop] {
if parent[nb] == -2 {
parent[nb] = b
queue = append(queue, nb)
}
}
}
}
return nil, false
}
func main() {
routes := [][]int{{1, 4, 9}, {9, 3}, {3, 8, 2}, {4, 7}}
for _, trip := range [][2]int{{1, 8}, {7, 1}, {1, 5}} {
taken, ok := fewestBuses(routes, trip[0], trip[1])
if !ok {
fmt.Printf("from %d to %d: -1\n", trip[0], trip[1])
continue
}
parts := []string{}
for _, b := range taken {
parts = append(parts, strconv.Itoa(b))
}
fmt.Printf("from %d to %d: %d buses (%s)\n", trip[0], trip[1], len(taken), strings.Join(parts, " "))
}
}
// from 1 to 8: 3 buses (0 1 2)
// from 7 to 1: 2 buses (3 0)
// from 1 to 5: -1From 1 to 8 takes buses 0, 1 and 2, changing at 9 and then at 3. From 7, bus 3 reaches 4, where bus 0 goes on to 1: 2 buses. Stop 5 is on no bus at all, so −1. The search also checks for the target as it reads each bus's stops, so it stops at the first bus that gets there.
![Four bus routes, [1, 4, 9], [9, 3], [3, 8, 2] and [4, 7], searched from stop 1 to stop 8 in three columns. 1 bus: bus 0, through the start, with stops 1, 4 and 9. 2 buses: bus 1, with 9 and 3, reached by changing at 9, and bus 3, with 4 and 7, reached by changing at 4, its link dashed, since it leads nowhere new. 3 buses: bus 2, with 3, 8 and 2, reached by changing at 3; it stops at 8, and the search ends there. Stop 1, the start, and stop 8 are ringed. The trip is bus 0, then bus 1, then bus 2: 3 buses. Focal line: count buses, not stops: one ride can pass many stops. Title: a step is a bus.](https://pub-a1b3030acfb94e84ba8a89fb182c53bc.r2.dev/public/dsa-content-292458c7-c6a4-466b-9d43-1895a5ce2978/a-step-is-a-bus.webp)
When BFS is the answer
| The question asks for | Search over | Start the queue with |
|---|---|---|
| The fewest moves, every move the same | Cells or vertices | The start, at 0 |
| The distance to the nearest of many, or the time to spread | Cells | Every source, at 0 |
| The fewest moves made by a rule | States, made as you go | The starting state |
| The fewest moves with something to spend | A cell and what's left | The start, with all of it |
| The least cost when a step costs 0 or 1 | Cells, on a deque | The start, at 0 |
| The fewest rides when one ride covers many stops | Buses | Every bus through the start |
Near misses: steps with other costs are Weighted Shortest Paths: Dijkstra, Bellman-Ford and Floyd-Warshall. Whether a path exists at all, or how many groups there are, needs no distances, so any search from Depth-First and Breadth-First Search will do. Every path, rather than the shortest, is backtracking, in Backtracking on Grids and Constraints.
Mistakes that look right
Two of these run below in every language, and two more ran above. The others are just as common:
- Counting a minute for the last layer: the oranges that rotted last rot nothing more, but a loop that counts every layer counts one minute too many.
- A start that's already a dead end: Open the Lock must answer −1 when 0000 is one, but the search turns the wheels from it anyway.
- Keeping the first arrival when steps cost 0 or 1: the plain queue above said 3 obstacles where 2 will do.
- Marking the cell when the state holds more: with a break to spend, marking cells alone took 10 steps where 8 will do.
- A search from each source: the right answers, for k times the work; put every source in the queue at once.
- Marking on the way out: a vertex goes in once for every neighbour that finds it first, as in Depth-First and Breadth-First Search.
- Word Ladder's neighbours by comparing every pair of words: the whole list for every word, before the search has even moved; change each letter instead.
- BFS on weighted edges: the fewest edges isn't the least cost.
from collections import deque
def minutes(crate, count_every_layer): # Rotting Oranges, one layer of the queue per minute
g = [row[:] for row in crate]
R, C = len(g), len(g[0])
queue = deque((r, c) for r in range(R) for c in range(C) if g[r][c] == 2)
fresh = sum(row.count(1) for row in g)
m = 0
while queue:
rotted = False
for _ in range(len(queue)): # everything that rotted the minute before
r, c = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and g[nr][nc] == 1:
g[nr][nc] = 2
fresh -= 1
rotted = True
queue.append((nr, nc))
if rotted or count_every_layer: # the last layer rots nothing: no minute for it
m += 1
return m if fresh == 0 else -1
def open_lock(deadends, target, check_start): # Open the Lock, with or without looking at 0000 first
dead = set(deadends)
if check_start and "0000" in dead:
return -1
dist = {"0000": 0}
queue = deque(["0000"])
while queue:
s = queue.popleft()
if s == target:
return dist[s]
for i in range(4):
for step in (1, -1):
t = s[:i] + str((int(s[i]) + step) % 10) + s[i + 1:]
if t not in dead and t not in dist:
dist[t] = dist[s] + 1
queue.append(t)
return -1
crate = [[1, 1, 1, 1],
[0, 0, 2, 1],
[1, 1, 1, 0]]
print("counting every layer:", minutes(crate, True), "minutes | only layers that rot something:",
minutes(crate, False))
print("a dead start, not checked:", open_lock(["0000"], "0100", False), "| checked:",
open_lock(["0000"], "0100", True))
# counting every layer: 4 minutes | only layers that rot something: 3
# a dead start, not checked: 1 | checked: -1import java.util.*;
public class Main {
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int minutes(int[][] crate, boolean countEveryLayer) { // Rotting Oranges, one layer per minute
int R = crate.length, C = crate[0].length;
int[][] g = new int[R][];
for (int r = 0; r < R; r++) g[r] = crate[r].clone();
ArrayDeque<int[]> queue = new ArrayDeque<>();
int fresh = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (g[r][c] == 2) queue.add(new int[] {r, c});
if (g[r][c] == 1) fresh++;
}
}
int m = 0;
while (!queue.isEmpty()) {
boolean rotted = false;
for (int i = queue.size(); i > 0; i--) { // everything that rotted the minute before
int[] cur = queue.poll();
for (int[] d : DIRS) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 1) {
g[nr][nc] = 2;
fresh--;
rotted = true;
queue.add(new int[] {nr, nc});
}
}
}
if (rotted || countEveryLayer) m++; // the last layer rots nothing: no minute for it
}
return fresh == 0 ? m : -1;
}
static int openLock(String[] deadends, String target, boolean checkStart) { // with or without looking at 0000
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
if (checkStart && dead.contains("0000")) return -1;
Map<String, Integer> dist = new HashMap<>();
dist.put("0000", 0);
ArrayDeque<String> queue = new ArrayDeque<>();
queue.add("0000");
while (!queue.isEmpty()) {
String s = queue.poll();
if (s.equals(target)) return dist.get(s);
for (int i = 0; i < 4; i++) {
for (int step : new int[] {1, -1}) {
char[] t = s.toCharArray();
t[i] = (char) ('0' + (t[i] - '0' + step + 10) % 10);
String next = new String(t);
if (!dead.contains(next) && !dist.containsKey(next)) {
dist.put(next, dist.get(s) + 1);
queue.add(next);
}
}
}
}
return -1;
}
public static void main(String[] args) {
int[][] crate = {{1, 1, 1, 1},
{0, 0, 2, 1},
{1, 1, 1, 0}};
System.out.println("counting every layer: " + minutes(crate, true)
+ " minutes | only layers that rot something: " + minutes(crate, false));
String[] dead = {"0000"};
System.out.println("a dead start, not checked: " + openLock(dead, "0100", false) + " | checked: "
+ openLock(dead, "0100", true));
}
}
// counting every layer: 4 minutes | only layers that rot something: 3
// a dead start, not checked: 1 | checked: -1#include <bits/stdc++.h>
using namespace std;
const int DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int minutes(vector<vector<int>> g, bool countEveryLayer) { // Rotting Oranges, one layer of the queue per minute
int R = g.size(), C = g[0].size(), fresh = 0;
queue<pair<int, int>> q;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (g[r][c] == 2) q.push({r, c});
if (g[r][c] == 1) fresh++;
}
}
int m = 0;
while (!q.empty()) {
bool rotted = false;
for (int i = q.size(); i > 0; i--) { // everything that rotted the minute before
auto [r, c] = q.front();
q.pop();
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 1) {
g[nr][nc] = 2;
fresh--;
rotted = true;
q.push({nr, nc});
}
}
}
if (rotted || countEveryLayer) m++; // the last layer rots nothing: no minute for it
}
return fresh == 0 ? m : -1;
}
int openLock(const vector<string>& deadends, const string& target, bool checkStart) { // look at 0000 first, or not
unordered_set<string> dead(deadends.begin(), deadends.end());
if (checkStart && dead.count("0000")) return -1;
unordered_map<string, int> dist = {{"0000", 0}};
queue<string> q;
q.push("0000");
while (!q.empty()) {
string s = q.front();
q.pop();
if (s == target) return dist[s];
for (int i = 0; i < 4; i++) {
for (int step : {1, -1}) {
string t = s;
t[i] = '0' + (s[i] - '0' + step + 10) % 10;
if (!dead.count(t) && !dist.count(t)) {
dist[t] = dist[s] + 1;
q.push(t);
}
}
}
}
return -1;
}
int main() {
vector<vector<int>> crate = {{1, 1, 1, 1},
{0, 0, 2, 1},
{1, 1, 1, 0}};
cout << "counting every layer: " << minutes(crate, true) << " minutes | only layers that rot something: "
<< minutes(crate, false) << "\n";
cout << "a dead start, not checked: " << openLock({"0000"}, "0100", false) << " | checked: "
<< openLock({"0000"}, "0100", true) << "\n";
}
// counting every layer: 4 minutes | only layers that rot something: 3
// a dead start, not checked: 1 | checked: -1function minutes(crate, countEveryLayer) { // Rotting Oranges, one layer of the queue per minute
const g = crate.map((row) => [...row]);
const R = g.length, C = g[0].length;
let queue = [], fresh = 0;
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (g[r][c] === 2) queue.push([r, c]);
if (g[r][c] === 1) fresh++;
}
}
let m = 0;
while (queue.length) {
let rotted = false;
const next = [];
for (const [r, c] of queue) { // everything that rotted the minute before
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] === 1) {
g[nr][nc] = 2;
fresh--;
rotted = true;
next.push([nr, nc]);
}
}
}
queue = next;
if (rotted || countEveryLayer) m++; // the last layer rots nothing: no minute for it
}
return fresh === 0 ? m : -1;
}
function openLock(deadends, target, checkStart) { // Open the Lock, with or without looking at 0000 first
const dead = new Set(deadends);
if (checkStart && dead.has("0000")) return -1;
const dist = new Map([["0000", 0]]);
const queue = ["0000"];
for (let head = 0; head < queue.length; head++) {
const s = queue[head];
if (s === target) return dist.get(s);
for (let i = 0; i < 4; i++) {
for (const step of [1, -1]) {
const t = s.slice(0, i) + String((Number(s[i]) + step + 10) % 10) + s.slice(i + 1);
if (!dead.has(t) && !dist.has(t)) {
dist.set(t, dist.get(s) + 1);
queue.push(t);
}
}
}
}
return -1;
}
const crate = [[1, 1, 1, 1],
[0, 0, 2, 1],
[1, 1, 1, 0]];
console.log(`counting every layer: ${minutes(crate, true)} minutes | only layers that rot something: ${
minutes(crate, false)}`);
console.log(`a dead start, not checked: ${openLock(["0000"], "0100", false)} | checked: ${
openLock(["0000"], "0100", true)}`);
// counting every layer: 4 minutes | only layers that rot something: 3
// a dead start, not checked: 1 | checked: -1function minutes(crate: number[][], countEveryLayer: boolean): number { // Rotting Oranges, a layer a minute
const g = crate.map((row) => [...row]);
const R = g.length, C = g[0].length;
let queue: [number, number][] = [], fresh = 0;
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (g[r][c] === 2) queue.push([r, c]);
if (g[r][c] === 1) fresh++;
}
}
let m = 0;
while (queue.length) {
let rotted = false;
const next: [number, number][] = [];
for (const [r, c] of queue) { // everything that rotted the minute before
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] === 1) {
g[nr][nc] = 2;
fresh--;
rotted = true;
next.push([nr, nc]);
}
}
}
queue = next;
if (rotted || countEveryLayer) m++; // the last layer rots nothing: no minute for it
}
return fresh === 0 ? m : -1;
}
function openLock(deadends: string[], target: string, checkStart: boolean): number { // look at 0000 first, or not
const dead = new Set(deadends);
if (checkStart && dead.has("0000")) return -1;
const dist = new Map<string, number>([["0000", 0]]);
const queue: string[] = ["0000"];
for (let head = 0; head < queue.length; head++) {
const s = queue[head];
if (s === target) return dist.get(s)!;
for (let i = 0; i < 4; i++) {
for (const step of [1, -1]) {
const t = s.slice(0, i) + String((Number(s[i]) + step + 10) % 10) + s.slice(i + 1);
if (!dead.has(t) && !dist.has(t)) {
dist.set(t, dist.get(s)! + 1);
queue.push(t);
}
}
}
}
return -1;
}
const crate: number[][] = [[1, 1, 1, 1],
[0, 0, 2, 1],
[1, 1, 1, 0]];
console.log(`counting every layer: ${minutes(crate, true)} minutes | only layers that rot something: ${
minutes(crate, false)}`);
console.log(`a dead start, not checked: ${openLock(["0000"], "0100", false)} | checked: ${
openLock(["0000"], "0100", true)}`);
// counting every layer: 4 minutes | only layers that rot something: 3
// a dead start, not checked: 1 | checked: -1using System;
using System.Collections.Generic;
class Program {
static readonly int[][] Dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
static int Minutes(int[,] crate, bool countEveryLayer) { // Rotting Oranges, one layer of the queue per minute
var g = (int[,]) crate.Clone();
int R = g.GetLength(0), C = g.GetLength(1), fresh = 0;
var queue = new Queue<(int r, int c)>();
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (g[r, c] == 2) queue.Enqueue((r, c));
if (g[r, c] == 1) fresh++;
}
}
int m = 0;
while (queue.Count > 0) {
bool rotted = false;
for (int i = queue.Count; i > 0; i--) { // everything that rotted the minute before
var (r, c) = queue.Dequeue();
foreach (int[] d in Dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr, nc] == 1) {
g[nr, nc] = 2;
fresh--;
rotted = true;
queue.Enqueue((nr, nc));
}
}
}
if (rotted || countEveryLayer) m++; // the last layer rots nothing: no minute for it
}
return fresh == 0 ? m : -1;
}
static int OpenLock(string[] deadends, string target, bool checkStart) { // with or without looking at 0000
var dead = new HashSet<string>(deadends);
if (checkStart && dead.Contains("0000")) return -1;
var dist = new Dictionary<string, int> { ["0000"] = 0 };
var queue = new Queue<string>();
queue.Enqueue("0000");
while (queue.Count > 0) {
string s = queue.Dequeue();
if (s == target) return dist[s];
for (int i = 0; i < 4; i++) {
foreach (int step in new[] {1, -1}) {
char[] t = s.ToCharArray();
t[i] = (char) ('0' + (t[i] - '0' + step + 10) % 10);
string next = new string(t);
if (!dead.Contains(next) && !dist.ContainsKey(next)) {
dist[next] = dist[s] + 1;
queue.Enqueue(next);
}
}
}
}
return -1;
}
static void Main() {
int[,] crate = { {1, 1, 1, 1},
{0, 0, 2, 1},
{1, 1, 1, 0} };
Console.WriteLine($"counting every layer: {Minutes(crate, true)} minutes | only layers that rot something: "
+ Minutes(crate, false));
var dead = new[] {"0000"};
Console.WriteLine($"a dead start, not checked: {OpenLock(dead, "0100", false)} | checked: "
+ OpenLock(dead, "0100", true));
}
}
// counting every layer: 4 minutes | only layers that rot something: 3
// a dead start, not checked: 1 | checked: -1package main
import "fmt"
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func minutes(crate [][]int, countEveryLayer bool) int { // Rotting Oranges, one layer of the queue per minute
R, C := len(crate), len(crate[0])
g := make([][]int, R)
queue := [][2]int{}
fresh := 0
for r := range crate {
g[r] = append([]int(nil), crate[r]...)
for c := 0; c < C; c++ {
if g[r][c] == 2 {
queue = append(queue, [2]int{r, c})
}
if g[r][c] == 1 {
fresh++
}
}
}
m := 0
for len(queue) > 0 {
rotted := false
next := [][2]int{}
for _, cur := range queue { // everything that rotted the minute before
for _, d := range dirs {
nr, nc := cur[0]+d[0], cur[1]+d[1]
if nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 1 {
g[nr][nc] = 2
fresh--
rotted = true
next = append(next, [2]int{nr, nc})
}
}
}
queue = next
if rotted || countEveryLayer { // the last layer rots nothing: no minute for it
m++
}
}
if fresh != 0 {
return -1
}
return m
}
func openLock(deadends []string, target string, checkStart bool) int { // with or without looking at 0000 first
dead := map[string]bool{}
for _, d := range deadends {
dead[d] = true
}
if checkStart && dead["0000"] {
return -1
}
dist := map[string]int{"0000": 0}
queue := []string{"0000"}
for head := 0; head < len(queue); head++ {
s := queue[head]
if s == target {
return dist[s]
}
for i := 0; i < 4; i++ {
for _, step := range []int{1, -1} {
t := []byte(s)
t[i] = byte('0' + (int(s[i]-'0')+step+10)%10)
next := string(t)
if _, seen := dist[next]; !dead[next] && !seen {
dist[next] = dist[s] + 1
queue = append(queue, next)
}
}
}
}
return -1
}
func main() {
crate := [][]int{
{1, 1, 1, 1},
{0, 0, 2, 1},
{1, 1, 1, 0},
}
fmt.Println("counting every layer:", minutes(crate, true), "minutes | only layers that rot something:",
minutes(crate, false))
fmt.Println("a dead start, not checked:", openLock([]string{"0000"}, "0100", false), "| checked:",
openLock([]string{"0000"}, "0100", true))
}
// counting every layer: 4 minutes | only layers that rot something: 3
// a dead start, not checked: 1 | checked: -1Counting every layer said 4 minutes for a crate that's all rotten after 3: the fourth layer held the last oranges to rot, and they rotted nothing. Count a minute only when something rots, or take the largest distance, as the BFS at the top of the page does. With 0000 a dead end the answer is −1; unchecked, the search started from it anyway and opened the lock in 1 turn.
Check yourself
Quiz
1 / 6Multiple choice
A crate is [[1, 1, 0, 2], [1, 0, 1, 1], [2, 1, 1, 0]], where 2 is rotten, 1 is fresh and 0 is empty. How many minutes until no orange is fresh?
Multiple choice
Why is the first time BFS reaches a vertex always by the fewest edges?
Multiple choice
01 Matrix asks for every cell's distance to its nearest 0. Which search finds all of them in one pass over the grid?
Multiple choice
Buses run the routes [[1, 2, 3, 4, 5], [1, 6], [6, 5], [5, 9]]. What is the fewest number of buses that gets you from stop 1 to stop 9?
Multiple choice
In 0-1 BFS, a cell is reached by a step that costs 0. Where does it go, and why?
Multiple choice
In a grid where you may break up to k walls on the way, what should the search mark as seen?
Practice
The problems in this group, each mapped to the idea it trains:
- Rotting Oranges: every rotten orange starts at once, and the answer is the last layer.
- 01 Matrix: every 0 at distance 0, in one pass.
- Walls and Gates: every gate at once, through empty rooms only.
- Shortest Path in Binary Matrix: eight moves, and the answer counts cells.
- Shortest Path in Unweighted Graph: distances from one source, −1 where it never gets.
- Minimum Steps via Multiply & Mod: the states are numbers below 100,000.
- Open the Lock: the states are combinations; check the start first.
- Word Ladder: the states are words, and the answer counts words.
- Word Ladder II: every shortest ladder, read back from the layers.