Depth-First and Breadth-First Search
Editorial
A photo of a million pixels
Flood fill is the paint bucket in an image editor: click a pixel and every pixel of the same colour joined to it changes. The first version anyone writes is a recursion: colour this pixel, then call yourself on each neighbour that has the old colour. Here it is on a photo of 1000 × 1000 pixels, all one colour, the same in every language:
R = C = 1000 # a photo of 1000 x 1000 pixels, all one colour
seen = [[False] * C for _ in range(R)]
deepest = 0
def fill(r, c, depth): # the flood fill everyone writes first
global deepest
deepest = max(deepest, depth)
seen[r][c] = True
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 not seen[nr][nc]:
fill(nr, nc, depth + 1)
print("pixels to fill:", R * C)
try:
fill(0, 0, 1)
print("filled", sum(row.count(True) for row in seen), "pixels, deepest call", deepest)
except RecursionError:
print("RecursionError at depth", deepest)
# pixels to fill: 1000000
# RecursionError at depth 999public class Main {
static final int R = 1000, C = 1000; // a photo of 1000 x 1000 pixels, all one colour
static boolean[][] seen = new boolean[R][C];
static int deepest = 0;
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static void fill(int r, int c, int depth) { // the flood fill everyone writes first
deepest = Math.max(deepest, depth);
seen[r][c] = true;
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !seen[nr][nc]) fill(nr, nc, depth + 1);
}
}
public static void main(String[] args) {
System.out.println("pixels to fill: " + R * C);
try {
fill(0, 0, 1);
int filled = 0;
for (boolean[] row : seen) for (boolean s : row) if (s) filled++;
System.out.println("filled " + filled + " pixels, deepest call " + deepest);
} catch (StackOverflowError e) {
System.out.println("StackOverflowError at depth " + deepest);
}
}
}
// pixels to fill: 1000000
// StackOverflowError at depth 7761#include <bits/stdc++.h>
using namespace std;
const int R = 1000, C = 1000; // a photo of 1000 x 1000 pixels, all one colour
vector<vector<bool>> seen(R, vector<bool>(C, false));
int deepest = 0;
const int DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void fill(int r, int c, int depth) { // the flood fill everyone writes first
deepest = max(deepest, depth);
seen[r][c] = true;
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !seen[nr][nc]) fill(nr, nc, depth + 1);
}
}
int main() {
cout << "pixels to fill: " << R * C << endl; // endl: out before anything can go wrong
fill(0, 0, 1);
long long filled = 0;
for (auto& row : seen) for (bool s : row) filled += s;
cout << "filled " << filled << " pixels, deepest call " << deepest << "\n";
}
// pixels to fill: 1000000
// filled 1000000 pixels, deepest call 1000000const R = 1000, C = 1000; // a photo of 1000 x 1000 pixels, all one colour
const seen = Array.from({ length: R }, () => new Array(C).fill(false));
let deepest = 0;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function fill(r, c, depth) { // the flood fill everyone writes first
deepest = Math.max(deepest, depth);
seen[r][c] = true;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !seen[nr][nc]) fill(nr, nc, depth + 1);
}
}
console.log(`pixels to fill: ${R * C}`);
try {
fill(0, 0, 1);
const filled = seen.reduce((n, row) => n + row.filter(Boolean).length, 0);
console.log(`filled ${filled} pixels, deepest call ${deepest}`);
} catch (e) {
console.log(`${e.name} at depth ${deepest}`);
}
// pixels to fill: 1000000
// RangeError at depth 4504const R = 1000, C = 1000; // a photo of 1000 x 1000 pixels, all one colour
const seen: boolean[][] = Array.from({ length: R }, () => new Array(C).fill(false));
let deepest = 0;
const DIRS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function fill(r: number, c: number, depth: number): void { // the flood fill everyone writes first
deepest = Math.max(deepest, depth);
seen[r][c] = true;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !seen[nr][nc]) fill(nr, nc, depth + 1);
}
}
console.log(`pixels to fill: ${R * C}`);
try {
fill(0, 0, 1);
const filled = seen.reduce((n, row) => n + row.filter(Boolean).length, 0);
console.log(`filled ${filled} pixels, deepest call ${deepest}`);
} catch (e) {
console.log(`${(e as Error).name} at depth ${deepest}`);
}
// pixels to fill: 1000000
// RangeError at depth 3217using System;
class Program {
const int R = 1000, C = 1000; // a photo of 1000 x 1000 pixels, all one colour
static bool[,] seen = new bool[R, C];
static int deepest = 0;
static readonly int[][] Dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
static void Fill(int r, int c, int depth) { // the flood fill everyone writes first
deepest = Math.Max(deepest, depth);
seen[r, c] = true;
foreach (int[] d in Dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !seen[nr, nc]) Fill(nr, nc, depth + 1);
}
}
static void Main() {
Console.WriteLine($"pixels to fill: {R * C}");
Fill(0, 0, 1);
int filled = 0;
foreach (bool s in seen) if (s) filled++;
Console.WriteLine($"filled {filled} pixels, deepest call {deepest}");
}
}
// pixels to fill: 1000000
// filled 1000000 pixels, deepest call 1000000package main
import "fmt"
const R, C = 1000, 1000 // a photo of 1000 x 1000 pixels, all one colour
var seen [R][C]bool
var deepest = 0
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func fill(r, c, depth int) { // the flood fill everyone writes first
if depth > deepest {
deepest = depth
}
seen[r][c] = true
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < R && nc >= 0 && nc < C && !seen[nr][nc] {
fill(nr, nc, depth+1)
}
}
}
func main() {
fmt.Println("pixels to fill:", R*C)
fill(0, 0, 1)
filled := 0
for _, row := range seen {
for _, s := range row {
if s {
filled++
}
}
}
fmt.Println("filled", filled, "pixels, deepest call", deepest)
}
// pixels to fill: 1000000
// filled 1000000 pixels, deepest call 1000000Four of the seven stopped short: Python at depth 999, with a RecursionError; TypeScript at depth 3,217, with a RangeError; JavaScript at depth 4,504, with a RangeError; Java at depth 7,761, with a StackOverflowError. Each language limits how deep calls can go, and this fill needs one call on top of the last for every pixel, a million deep, because each pixel is reached from the one before it. C++, C# and Go got all the way through: here they run with a big stack, and Go grows its stacks as they fill. How deep a recursion can go depends on the language and on the stack the machine gives it, so a fill that passes here can crash somewhere else.
The fix is to keep the waiting pixels yourself. Here's the same fill with its own stack, and with a queue:
import time
from collections import deque
R = C = 1000
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
def fill(take): # take: which end of the waiting list a cell comes off
seen = [[False] * C for _ in range(R)]
waiting = deque([(0, 0)])
seen[0][0] = True
filled, most = 0, 1
while waiting:
r, c = take(waiting)
filled += 1
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and not seen[nr][nc]:
seen[nr][nc] = True # marked as it goes in, so it goes in once
waiting.append((nr, nc))
most = max(most, len(waiting))
return filled, most
for name, take in (("stack", deque.pop), ("queue", deque.popleft)): # newest first, oldest first
start = time.perf_counter()
filled, most = fill(take)
ms = round((time.perf_counter() - start) * 1000)
print(f"{name}: {filled} pixels, at most {most} waiting, {ms} ms")
# stack: 1000000 pixels, at most 499501 waiting, 700 ms
# queue: 1000000 pixels, at most 1000 waiting, 635 msimport java.util.*;
public class Main {
static final int R = 1000, C = 1000;
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int[] fill(boolean newestFirst) { // a stack gives back its newest cell, a queue its oldest
boolean[][] seen = new boolean[R][C];
ArrayDeque<int[]> waiting = new ArrayDeque<>();
waiting.addLast(new int[] {0, 0});
seen[0][0] = true;
int filled = 0, most = 1;
while (!waiting.isEmpty()) {
int[] cell = newestFirst ? waiting.pollLast() : waiting.pollFirst();
filled++;
for (int[] d : DIRS) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !seen[nr][nc]) {
seen[nr][nc] = true; // marked as it goes in, so it goes in once
waiting.addLast(new int[] {nr, nc});
}
}
most = Math.max(most, waiting.size());
}
return new int[] {filled, most};
}
public static void main(String[] args) {
for (String name : new String[] {"stack", "queue"}) {
long start = System.nanoTime();
int[] got = fill(name.equals("stack"));
long ms = (System.nanoTime() - start) / 1000000;
System.out.println(name + ": " + got[0] + " pixels, at most " + got[1] + " waiting, " + ms + " ms");
}
}
}
// stack: 1000000 pixels, at most 499501 waiting, 113 ms
// queue: 1000000 pixels, at most 1000 waiting, 59 ms#include <bits/stdc++.h>
using namespace std;
const int R = 1000, C = 1000;
const int DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
pair<int, int> fill(bool newestFirst) { // a stack gives back its newest cell, a queue its oldest
vector<vector<bool>> seen(R, vector<bool>(C, false));
deque<pair<int, int>> waiting = {{0, 0}};
seen[0][0] = true;
int filled = 0, most = 1;
while (!waiting.empty()) {
auto [r, c] = newestFirst ? waiting.back() : waiting.front();
if (newestFirst) waiting.pop_back(); else waiting.pop_front();
filled++;
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !seen[nr][nc]) {
seen[nr][nc] = true; // marked as it goes in, so it goes in once
waiting.push_back({nr, nc});
}
}
most = max(most, (int) waiting.size());
}
return {filled, most};
}
int main() {
for (string name : {"stack", "queue"}) {
auto start = chrono::steady_clock::now();
auto [filled, most] = fill(name == "stack");
long long ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
cout << name << ": " << filled << " pixels, at most " << most << " waiting, " << ms << " ms\n";
}
}
// stack: 1000000 pixels, at most 499501 waiting, 18 ms
// queue: 1000000 pixels, at most 1000 waiting, 14 msconst R = 1000, C = 1000;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function fill(newestFirst) { // a stack gives back its newest cell, a queue its oldest
const seen = Array.from({ length: R }, () => new Uint8Array(C));
const waiting = [[0, 0]]; // a queue reads from head and never shifts
let head = 0, filled = 0, most = 1;
seen[0][0] = 1;
while (head < waiting.length) {
const [r, c] = newestFirst ? waiting.pop() : waiting[head++];
filled++;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !seen[nr][nc]) {
seen[nr][nc] = 1; // marked as it goes in, so it goes in once
waiting.push([nr, nc]);
}
}
most = Math.max(most, waiting.length - head);
}
return [filled, most];
}
for (const name of ["stack", "queue"]) {
const start = performance.now();
const [filled, most] = fill(name === "stack");
const ms = Math.round(performance.now() - start);
console.log(`${name}: ${filled} pixels, at most ${most} waiting, ${ms} ms`);
}
// stack: 1000000 pixels, at most 499501 waiting, 222 ms
// queue: 1000000 pixels, at most 1000 waiting, 348 msconst R = 1000, C = 1000;
const DIRS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function fill(newestFirst: boolean): [number, number] { // a stack gives back its newest cell, a queue its oldest
const seen: Uint8Array[] = Array.from({ length: R }, () => new Uint8Array(C));
const waiting: [number, number][] = [[0, 0]]; // a queue reads from head and never shifts
let head = 0, filled = 0, most = 1;
seen[0][0] = 1;
while (head < waiting.length) {
const [r, c] = newestFirst ? waiting.pop()! : waiting[head++];
filled++;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !seen[nr][nc]) {
seen[nr][nc] = 1; // marked as it goes in, so it goes in once
waiting.push([nr, nc]);
}
}
most = Math.max(most, waiting.length - head);
}
return [filled, most];
}
for (const name of ["stack", "queue"]) {
const start = performance.now();
const [filled, most] = fill(name === "stack");
const ms = Math.round(performance.now() - start);
console.log(`${name}: ${filled} pixels, at most ${most} waiting, ${ms} ms`);
}
// stack: 1000000 pixels, at most 499501 waiting, 200 ms
// queue: 1000000 pixels, at most 1000 waiting, 394 msusing System;
using System.Collections.Generic;
using System.Diagnostics;
class Program {
const int R = 1000, C = 1000;
static readonly int[][] Dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
static int[] Fill(bool newestFirst) { // a stack gives back its newest cell, a queue its oldest
var seen = new bool[R, C];
var waiting = new LinkedList<int[]>();
waiting.AddLast(new[] {0, 0});
seen[0, 0] = true;
int filled = 0, most = 1;
while (waiting.Count > 0) {
var node = newestFirst ? waiting.Last : waiting.First;
waiting.Remove(node);
int[] cell = node.Value;
filled++;
foreach (int[] d in Dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !seen[nr, nc]) {
seen[nr, nc] = true; // marked as it goes in, so it goes in once
waiting.AddLast(new[] {nr, nc});
}
}
most = Math.Max(most, waiting.Count);
}
return new[] {filled, most};
}
static void Main() {
foreach (string name in new[] {"stack", "queue"}) {
var watch = Stopwatch.StartNew();
int[] got = Fill(name == "stack");
Console.WriteLine($"{name}: {got[0]} pixels, at most {got[1]} waiting, {watch.ElapsedMilliseconds} ms");
}
}
}
// stack: 1000000 pixels, at most 499501 waiting, 247 ms
// queue: 1000000 pixels, at most 1000 waiting, 66 mspackage main
import (
"fmt"
"time"
)
const R, C = 1000, 1000
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func fill(newestFirst bool) (int, int) { // a stack gives back its newest cell, a queue its oldest
seen := make([][]bool, R)
for i := range seen {
seen[i] = make([]bool, C)
}
waiting := [][2]int{{0, 0}} // a queue reads from head and never shifts
head, filled, most := 0, 0, 1
seen[0][0] = true
for head < len(waiting) {
var cell [2]int
if newestFirst {
cell = waiting[len(waiting)-1]
waiting = waiting[:len(waiting)-1]
} else {
cell = waiting[head]
head++
}
filled++
for _, d := range dirs {
nr, nc := cell[0]+d[0], cell[1]+d[1]
if nr >= 0 && nr < R && nc >= 0 && nc < C && !seen[nr][nc] {
seen[nr][nc] = true // marked as it goes in, so it goes in once
waiting = append(waiting, [2]int{nr, nc})
}
}
if len(waiting)-head > most {
most = len(waiting) - head
}
}
return filled, most
}
func main() {
for _, name := range []string{"stack", "queue"} {
start := time.Now()
filled, most := fill(name == "stack")
fmt.Printf("%s: %d pixels, at most %d waiting, %d ms\n", name, filled, most, time.Since(start).Milliseconds())
}
}
// stack: 1000000 pixels, at most 499501 waiting, 54 ms
// queue: 1000000 pixels, at most 1000 waiting, 103 msBoth coloured all 1,000,000 pixels in every language, in 700 and 635 ms in Python. The only difference between them is which end of the waiting list the next pixel comes from: the newest (a stack) or the oldest (a queue). That one choice is the whole difference between depth-first and breadth-first search. It changes the order the pixels are coloured in, and how many wait at once: the queue never held more than 1,000, one diagonal line across the photo, while the stack held 499,501, nearly half of it.
Deep or wide
A search needs two things: a waiting list of vertices found but not looked at yet, and a mark on every vertex found, so nothing is found twice. Then one loop: take a vertex off the list, and put each of its unmarked neighbours on, marking them as they go.
- Depth-first search (DFS) takes the newest vertex each time, so it runs down one path as far as it goes, then backs up to the last place with something left. A recursion does the same, with the call stack as its waiting list.
- Breadth-first search (BFS) takes the oldest, so it spreads out in rings: every vertex one edge away, then every vertex two edges away, and so on.
On a graph of seven vertices, from 0, with each list in the order its edges were given:
from collections import deque
n = 7
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (4, 6), (5, 6)]
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
order, seen = [], [False] * n
def dfs(u): # the call stack is the waiting list
seen[u] = True
order.append(u)
for v in graph[u]:
if not seen[v]:
dfs(v)
dfs(0)
print("recursive DFS from 0:", " ".join(map(str, order)))
order, seen, stack = [], [False] * n, [0]
while stack:
u = stack.pop() # the newest first
if seen[u]:
continue # put in twice, taken once
seen[u] = True
order.append(u)
for v in reversed(graph[u]): # reversed, so the first neighbour comes out first
if not seen[v]:
stack.append(v)
print("DFS with a stack: ", " ".join(map(str, order)))
layer = [-1] * n
layer[0] = 0
order, queue = [], deque([0])
while queue:
u = queue.popleft() # the oldest first
order.append(u)
for v in graph[u]:
if layer[v] == -1: # marked as it goes in
layer[v] = layer[u] + 1
queue.append(v)
print("BFS from 0: ", " ".join(map(str, order)))
print("BFS layers:", " | ".join(" ".join(str(u) for u in range(n) if layer[u] == d) for d in range(max(layer) + 1)))
# recursive DFS from 0: 0 1 3 4 6 5 2
# DFS with a stack: 0 1 3 4 6 5 2
# BFS from 0: 0 1 2 3 4 5 6
# BFS layers: 0 | 1 2 | 3 4 5 | 6import java.util.*;
public class Main {
static int n = 7;
static List<List<Integer>> graph = new ArrayList<>();
static List<Integer> order = new ArrayList<>();
static boolean[] seen = new boolean[n];
static void dfs(int u) { // the call stack is the waiting list
seen[u] = true;
order.add(u);
for (int v : graph.get(u)) if (!seen[v]) dfs(v);
}
static String joined(List<Integer> values) {
StringJoiner s = new StringJoiner(" ");
for (int v : values) s.add(String.valueOf(v));
return s.toString();
}
public static void main(String[] args) {
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {4, 6}, {5, 6}};
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]);
}
dfs(0);
System.out.println("recursive DFS from 0: " + joined(order));
order = new ArrayList<>();
seen = new boolean[n];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
while (!stack.isEmpty()) {
int u = stack.pop(); // the newest first
if (seen[u]) continue; // put in twice, taken once
seen[u] = true;
order.add(u);
List<Integer> nbrs = graph.get(u);
for (int i = nbrs.size() - 1; i >= 0; i--) { // reversed, so the first neighbour comes out first
if (!seen[nbrs.get(i)]) stack.push(nbrs.get(i));
}
}
System.out.println("DFS with a stack: " + joined(order));
int[] layer = new int[n];
Arrays.fill(layer, -1);
layer[0] = 0;
order = new ArrayList<>();
Deque<Integer> queue = new ArrayDeque<>();
queue.add(0);
while (!queue.isEmpty()) {
int u = queue.poll(); // the oldest first
order.add(u);
for (int v : graph.get(u)) {
if (layer[v] == -1) { // marked as it goes in
layer[v] = layer[u] + 1;
queue.add(v);
}
}
}
System.out.println("BFS from 0: " + joined(order));
StringJoiner layers = new StringJoiner(" | ");
int deepest = Arrays.stream(layer).max().getAsInt();
for (int d = 0; d <= deepest; d++) {
List<Integer> at = new ArrayList<>();
for (int u = 0; u < n; u++) if (layer[u] == d) at.add(u);
layers.add(joined(at));
}
System.out.println("BFS layers: " + layers);
}
}
// recursive DFS from 0: 0 1 3 4 6 5 2
// DFS with a stack: 0 1 3 4 6 5 2
// BFS from 0: 0 1 2 3 4 5 6
// BFS layers: 0 | 1 2 | 3 4 5 | 6#include <bits/stdc++.h>
using namespace std;
int n = 7;
vector<vector<int>> graph(n);
vector<int> order;
vector<bool> seen(n, false);
void dfs(int u) { // the call stack is the waiting list
seen[u] = true;
order.push_back(u);
for (int v : graph[u]) if (!seen[v]) dfs(v);
}
string joined(const vector<int>& values) {
string s;
for (size_t i = 0; i < values.size(); i++) s += (i ? " " : "") + to_string(values[i]);
return s;
}
int main() {
vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {4, 6}, {5, 6}};
for (auto [u, v] : edges) {
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(0);
cout << "recursive DFS from 0: " << joined(order) << "\n";
order.clear();
seen.assign(n, false);
vector<int> stack = {0};
while (!stack.empty()) {
int u = stack.back(); // the newest first
stack.pop_back();
if (seen[u]) continue; // put in twice, taken once
seen[u] = true;
order.push_back(u);
for (int i = (int) graph[u].size() - 1; i >= 0; i--) { // reversed, so the first neighbour comes out first
if (!seen[graph[u][i]]) stack.push_back(graph[u][i]);
}
}
cout << "DFS with a stack: " << joined(order) << "\n";
vector<int> layer(n, -1);
layer[0] = 0;
order.clear();
queue<int> q;
q.push(0);
while (!q.empty()) {
int u = q.front(); // the oldest first
q.pop();
order.push_back(u);
for (int v : graph[u]) {
if (layer[v] == -1) { // marked as it goes in
layer[v] = layer[u] + 1;
q.push(v);
}
}
}
cout << "BFS from 0: " << joined(order) << "\n";
int deepest = *max_element(layer.begin(), layer.end());
cout << "BFS layers: ";
for (int d = 0; d <= deepest; d++) {
vector<int> at;
for (int u = 0; u < n; u++) if (layer[u] == d) at.push_back(u);
cout << (d ? " | " : "") << joined(at);
}
cout << "\n";
}
// recursive DFS from 0: 0 1 3 4 6 5 2
// DFS with a stack: 0 1 3 4 6 5 2
// BFS from 0: 0 1 2 3 4 5 6
// BFS layers: 0 | 1 2 | 3 4 5 | 6const n = 7;
const edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [4, 6], [5, 6]];
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
let order = [], seen = new Array(n).fill(false);
function dfs(u) { // the call stack is the waiting list
seen[u] = true;
order.push(u);
for (const v of graph[u]) if (!seen[v]) dfs(v);
}
dfs(0);
console.log(`recursive DFS from 0: ${order.join(" ")}`);
order = [];
seen = new Array(n).fill(false);
const stack = [0];
while (stack.length) {
const u = stack.pop(); // the newest first
if (seen[u]) continue; // put in twice, taken once
seen[u] = true;
order.push(u);
for (const v of [...graph[u]].reverse()) { // reversed, so the first neighbour comes out first
if (!seen[v]) stack.push(v);
}
}
console.log(`DFS with a stack: ${order.join(" ")}`);
const layer = new Array(n).fill(-1);
layer[0] = 0;
order = [];
const queue = [0];
for (let head = 0; head < queue.length; head++) {
const u = queue[head]; // the oldest first
order.push(u);
for (const v of graph[u]) {
if (layer[v] === -1) { // marked as it goes in
layer[v] = layer[u] + 1;
queue.push(v);
}
}
}
console.log(`BFS from 0: ${order.join(" ")}`);
const layers = [];
for (let d = 0; d <= Math.max(...layer); d++) {
layers.push([...Array(n).keys()].filter((u) => layer[u] === d).join(" "));
}
console.log(`BFS layers: ${layers.join(" | ")}`);
// recursive DFS from 0: 0 1 3 4 6 5 2
// DFS with a stack: 0 1 3 4 6 5 2
// BFS from 0: 0 1 2 3 4 5 6
// BFS layers: 0 | 1 2 | 3 4 5 | 6const n = 7;
const edges: [number, number][] = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [4, 6], [5, 6]];
const graph: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
let order: number[] = [], seen: boolean[] = new Array(n).fill(false);
function dfs(u: number): void { // the call stack is the waiting list
seen[u] = true;
order.push(u);
for (const v of graph[u]) if (!seen[v]) dfs(v);
}
dfs(0);
console.log(`recursive DFS from 0: ${order.join(" ")}`);
order = [];
seen = new Array(n).fill(false);
const stack: number[] = [0];
while (stack.length) {
const u = stack.pop()!; // the newest first
if (seen[u]) continue; // put in twice, taken once
seen[u] = true;
order.push(u);
for (const v of [...graph[u]].reverse()) { // reversed, so the first neighbour comes out first
if (!seen[v]) stack.push(v);
}
}
console.log(`DFS with a stack: ${order.join(" ")}`);
const layer: number[] = new Array(n).fill(-1);
layer[0] = 0;
order = [];
const queue: number[] = [0];
for (let head = 0; head < queue.length; head++) {
const u = queue[head]; // the oldest first
order.push(u);
for (const v of graph[u]) {
if (layer[v] === -1) { // marked as it goes in
layer[v] = layer[u] + 1;
queue.push(v);
}
}
}
console.log(`BFS from 0: ${order.join(" ")}`);
const layers: string[] = [];
for (let d = 0; d <= Math.max(...layer); d++) {
layers.push([...Array(n).keys()].filter((u) => layer[u] === d).join(" "));
}
console.log(`BFS layers: ${layers.join(" | ")}`);
// recursive DFS from 0: 0 1 3 4 6 5 2
// DFS with a stack: 0 1 3 4 6 5 2
// BFS from 0: 0 1 2 3 4 5 6
// BFS layers: 0 | 1 2 | 3 4 5 | 6using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static int n = 7;
static List<int>[] graph = new List<int>[n];
static List<int> order = new List<int>();
static bool[] seen = new bool[n];
static void Dfs(int u) { // the call stack is the waiting list
seen[u] = true;
order.Add(u);
foreach (int v in graph[u]) if (!seen[v]) Dfs(v);
}
static void Main() {
int[][] edges = { new[] {0, 1}, new[] {0, 2}, new[] {1, 3}, new[] {1, 4}, new[] {2, 5}, new[] {4, 6},
new[] {5, 6} };
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]);
}
Dfs(0);
Console.WriteLine("recursive DFS from 0: " + string.Join(" ", order));
order = new List<int>();
seen = new bool[n];
var stack = new Stack<int>();
stack.Push(0);
while (stack.Count > 0) {
int u = stack.Pop(); // the newest first
if (seen[u]) continue; // put in twice, taken once
seen[u] = true;
order.Add(u);
for (int i = graph[u].Count - 1; i >= 0; i--) { // reversed, so the first neighbour comes out first
if (!seen[graph[u][i]]) stack.Push(graph[u][i]);
}
}
Console.WriteLine("DFS with a stack: " + string.Join(" ", order));
int[] layer = Enumerable.Repeat(-1, n).ToArray();
layer[0] = 0;
order = new List<int>();
var queue = new Queue<int>();
queue.Enqueue(0);
while (queue.Count > 0) {
int u = queue.Dequeue(); // the oldest first
order.Add(u);
foreach (int v in graph[u]) {
if (layer[v] == -1) { // marked as it goes in
layer[v] = layer[u] + 1;
queue.Enqueue(v);
}
}
}
Console.WriteLine("BFS from 0: " + string.Join(" ", order));
var layers = new List<string>();
for (int d = 0; d <= layer.Max(); d++) {
layers.Add(string.Join(" ", Enumerable.Range(0, n).Where(u => layer[u] == d)));
}
Console.WriteLine("BFS layers: " + string.Join(" | ", layers));
}
}
// recursive DFS from 0: 0 1 3 4 6 5 2
// DFS with a stack: 0 1 3 4 6 5 2
// BFS from 0: 0 1 2 3 4 5 6
// BFS layers: 0 | 1 2 | 3 4 5 | 6package main
import (
"fmt"
"strconv"
"strings"
)
var n = 7
var graph = make([][]int, n)
var order []int
var seen = make([]bool, n)
func dfs(u int) { // the call stack is the waiting list
seen[u] = true
order = append(order, u)
for _, v := range graph[u] {
if !seen[v] {
dfs(v)
}
}
}
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() {
edges := [][2]int{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {4, 6}, {5, 6}}
for _, e := range edges {
graph[e[0]] = append(graph[e[0]], e[1])
graph[e[1]] = append(graph[e[1]], e[0])
}
dfs(0)
fmt.Println("recursive DFS from 0: " + joined(order))
order = nil
seen = make([]bool, n)
stack := []int{0}
for len(stack) > 0 {
u := stack[len(stack)-1] // the newest first
stack = stack[:len(stack)-1]
if seen[u] {
continue // put in twice, taken once
}
seen[u] = true
order = append(order, u)
for i := len(graph[u]) - 1; i >= 0; i-- { // reversed, so the first neighbour comes out first
if !seen[graph[u][i]] {
stack = append(stack, graph[u][i])
}
}
}
fmt.Println("DFS with a stack: " + joined(order))
layer := make([]int, n)
for i := range layer {
layer[i] = -1
}
layer[0] = 0
order = nil
queue := []int{0}
for head := 0; head < len(queue); head++ {
u := queue[head] // the oldest first
order = append(order, u)
for _, v := range graph[u] {
if layer[v] == -1 { // marked as it goes in
layer[v] = layer[u] + 1
queue = append(queue, v)
}
}
}
fmt.Println("BFS from 0: " + joined(order))
deepest := 0
for _, d := range layer {
if d > deepest {
deepest = d
}
}
layers := []string{}
for d := 0; d <= deepest; d++ {
at := []int{}
for u := 0; u < n; u++ {
if layer[u] == d {
at = append(at, u)
}
}
layers = append(layers, joined(at))
}
fmt.Println("BFS layers: " + strings.Join(layers, " | "))
}
// recursive DFS from 0: 0 1 3 4 6 5 2
// DFS with a stack: 0 1 3 4 6 5 2
// BFS from 0: 0 1 2 3 4 5 6
// BFS layers: 0 | 1 2 | 3 4 5 | 6DFS went 0, 1, 3, then back up to 1 and down again through 4, 6 and 5 to 2: one path as deep as it goes, then the next. The version with its own stack visits in exactly the same order, because it pushes the neighbours in reverse, so the first one comes out first, and it skips a vertex that comes out a second time. BFS went in layers: 0; then 1 and 2, one edge away; then 3, 4 and 5; then 6. A vertex's layer is its number of edges from the start, which is why BFS finds the fewest steps, the subject of Shortest Paths with BFS.
DFS or BFS. Be the waiting list yourself: at every step, take the cell that comes out next, from a stack or from a queue, and watch the order it paints on the grid.
Why each vertex is found once
Every vertex that can be reached gets found: it goes on the list the first time one of its neighbours comes off, and everything on the list comes off in the end. And it's found once, because it's marked the moment it goes on. So each vertex comes off once and its list is read once: O(V + E) on adjacency lists, O(R × C) on a grid of R rows and C columns, where a cell has at most four neighbours. The marks take O(V) memory, and the waiting list as much at worst.
Mark a vertex when it goes in, not when it comes out. Marked on the way out, a vertex can go in once for every neighbour that finds it first: under Mistakes that look right, that's 1,741 pushes for 900 cells. The DFS with its own stack above is the one that marks on the way out, on purpose, to visit in the recursion's order; its stack can hold as many entries as there are edges.
One search per group
One search reaches the vertices joined to its start, and nothing else. To find every group, called a connected component, loop over the vertices and start a new search from each one no search has reached yet. The number of searches started is the number of groups:
def components(n, neighbours): # one search from every vertex no search has reached
seen, groups = [False] * n, []
for s in range(n):
if seen[s]:
continue
seen[s], group, stack = True, [], [s]
while stack:
u = stack.pop()
group.append(u)
for v in neighbours(u):
if not seen[v]:
seen[v] = True
stack.append(v)
groups.append(sorted(group))
return groups
def shown(groups):
return " ".join("[" + " ".join(map(str, g)) + "]" for g in groups) + f" -> {len(groups)}"
n, edges = 8, [(0, 1), (1, 2), (3, 4), (5, 6), (6, 7), (7, 5)]
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
print("components of 8 vertices:", shown(components(n, lambda u: graph[u])))
is_connected = [[1, 0, 0, 1, 0], # Number of Provinces hands over a matrix
[0, 1, 1, 0, 0],
[0, 1, 1, 0, 0],
[1, 0, 0, 1, 0],
[0, 0, 0, 0, 1]]
print("provinces from the matrix:", shown(components(5, lambda u: [v for v in range(5) if v != u and is_connected[u][v]])))
# components of 8 vertices: [0 1 2] [3 4] [5 6 7] -> 3
# provinces from the matrix: [0 3] [1 2] [4] -> 3import java.util.*;
import java.util.function.IntFunction;
public class Main {
static List<List<Integer>> components(int n, IntFunction<List<Integer>> neighbours) {
boolean[] seen = new boolean[n]; // one search from every vertex no search has reached
List<List<Integer>> groups = new ArrayList<>();
for (int s = 0; s < n; s++) {
if (seen[s]) continue;
seen[s] = true;
List<Integer> group = new ArrayList<>();
Deque<Integer> stack = new ArrayDeque<>();
stack.push(s);
while (!stack.isEmpty()) {
int u = stack.pop();
group.add(u);
for (int v : neighbours.apply(u)) {
if (!seen[v]) {
seen[v] = true;
stack.push(v);
}
}
}
Collections.sort(group);
groups.add(group);
}
return groups;
}
static String shown(List<List<Integer>> groups) {
StringJoiner s = new StringJoiner(" ");
for (List<Integer> g : groups) {
StringJoiner inner = new StringJoiner(" ", "[", "]");
for (int v : g) inner.add(String.valueOf(v));
s.add(inner.toString());
}
return s + " -> " + groups.size();
}
public static void main(String[] args) {
int n = 8;
int[][] edges = {{0, 1}, {1, 2}, {3, 4}, {5, 6}, {6, 7}, {7, 5}};
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]);
}
System.out.println("components of 8 vertices: " + shown(components(n, graph::get)));
int[][] isConnected = {{1, 0, 0, 1, 0}, // Number of Provinces hands over a matrix
{0, 1, 1, 0, 0},
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 0},
{0, 0, 0, 0, 1}};
System.out.println("provinces from the matrix: " + shown(components(5, u -> {
List<Integer> out = new ArrayList<>();
for (int v = 0; v < 5; v++) if (v != u && isConnected[u][v] == 1) out.add(v);
return out;
})));
}
}
// components of 8 vertices: [0 1 2] [3 4] [5 6 7] -> 3
// provinces from the matrix: [0 3] [1 2] [4] -> 3#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> components(int n, function<vector<int>(int)> neighbours) {
vector<bool> seen(n, false); // one search from every vertex no search has reached
vector<vector<int>> groups;
for (int s = 0; s < n; s++) {
if (seen[s]) continue;
seen[s] = true;
vector<int> group, stack = {s};
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
group.push_back(u);
for (int v : neighbours(u)) {
if (!seen[v]) {
seen[v] = true;
stack.push_back(v);
}
}
}
sort(group.begin(), group.end());
groups.push_back(group);
}
return groups;
}
string shown(const vector<vector<int>>& groups) {
string s;
for (size_t k = 0; k < groups.size(); k++) {
s += k ? " [" : "[";
for (size_t i = 0; i < groups[k].size(); i++) s += (i ? " " : "") + to_string(groups[k][i]);
s += "]";
}
return s + " -> " + to_string(groups.size());
}
int main() {
int n = 8;
vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {3, 4}, {5, 6}, {6, 7}, {7, 5}};
vector<vector<int>> graph(n);
for (auto [u, v] : edges) {
graph[u].push_back(v);
graph[v].push_back(u);
}
cout << "components of 8 vertices: " << shown(components(n, [&](int u) { return graph[u]; })) << "\n";
vector<vector<int>> isConnected = {{1, 0, 0, 1, 0}, // Number of Provinces hands over a matrix
{0, 1, 1, 0, 0},
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 0},
{0, 0, 0, 0, 1}};
cout << "provinces from the matrix: " << shown(components(5, [&](int u) {
vector<int> out;
for (int v = 0; v < 5; v++) if (v != u && isConnected[u][v]) out.push_back(v);
return out;
})) << "\n";
}
// components of 8 vertices: [0 1 2] [3 4] [5 6 7] -> 3
// provinces from the matrix: [0 3] [1 2] [4] -> 3function components(n, neighbours) { // one search from every vertex no search has reached
const seen = new Array(n).fill(false), groups = [];
for (let s = 0; s < n; s++) {
if (seen[s]) continue;
seen[s] = true;
const group = [], stack = [s];
while (stack.length) {
const u = stack.pop();
group.push(u);
for (const v of neighbours(u)) {
if (!seen[v]) {
seen[v] = true;
stack.push(v);
}
}
}
groups.push(group.sort((a, b) => a - b));
}
return groups;
}
const shown = (groups) => groups.map((g) => `[${g.join(" ")}]`).join(" ") + ` -> ${groups.length}`;
const n = 8, edges = [[0, 1], [1, 2], [3, 4], [5, 6], [6, 7], [7, 5]];
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
console.log(`components of 8 vertices: ${shown(components(n, (u) => graph[u]))}`);
const isConnected = [[1, 0, 0, 1, 0], // Number of Provinces hands over a matrix
[0, 1, 1, 0, 0],
[0, 1, 1, 0, 0],
[1, 0, 0, 1, 0],
[0, 0, 0, 0, 1]];
const provinces = components(5, (u) => [0, 1, 2, 3, 4].filter((v) => v !== u && isConnected[u][v]));
console.log(`provinces from the matrix: ${shown(provinces)}`);
// components of 8 vertices: [0 1 2] [3 4] [5 6 7] -> 3
// provinces from the matrix: [0 3] [1 2] [4] -> 3function components(n: number, neighbours: (u: number) => number[]): number[][] {
const seen: boolean[] = new Array(n).fill(false), groups: number[][] = []; // one search per vertex not reached
for (let s = 0; s < n; s++) {
if (seen[s]) continue;
seen[s] = true;
const group: number[] = [], stack: number[] = [s];
while (stack.length) {
const u = stack.pop()!;
group.push(u);
for (const v of neighbours(u)) {
if (!seen[v]) {
seen[v] = true;
stack.push(v);
}
}
}
groups.push(group.sort((a, b) => a - b));
}
return groups;
}
const shown = (groups: number[][]): string => groups.map((g) => `[${g.join(" ")}]`).join(" ") + ` -> ${groups.length}`;
const n = 8, edges: [number, number][] = [[0, 1], [1, 2], [3, 4], [5, 6], [6, 7], [7, 5]];
const graph: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
console.log(`components of 8 vertices: ${shown(components(n, (u) => graph[u]))}`);
const isConnected: number[][] = [[1, 0, 0, 1, 0], // Number of Provinces hands over a matrix
[0, 1, 1, 0, 0],
[0, 1, 1, 0, 0],
[1, 0, 0, 1, 0],
[0, 0, 0, 0, 1]];
const provinces = components(5, (u) => [0, 1, 2, 3, 4].filter((v) => v !== u && isConnected[u][v] === 1));
console.log(`provinces from the matrix: ${shown(provinces)}`);
// components of 8 vertices: [0 1 2] [3 4] [5 6 7] -> 3
// provinces from the matrix: [0 3] [1 2] [4] -> 3using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static List<List<int>> Components(int n, Func<int, IEnumerable<int>> neighbours) {
var seen = new bool[n]; // one search from every vertex no search has reached
var groups = new List<List<int>>();
for (int s = 0; s < n; s++) {
if (seen[s]) continue;
seen[s] = true;
var group = new List<int>();
var stack = new Stack<int>();
stack.Push(s);
while (stack.Count > 0) {
int u = stack.Pop();
group.Add(u);
foreach (int v in neighbours(u)) {
if (!seen[v]) {
seen[v] = true;
stack.Push(v);
}
}
}
group.Sort();
groups.Add(group);
}
return groups;
}
static string Shown(List<List<int>> groups) {
return string.Join(" ", groups.Select(g => "[" + string.Join(" ", g) + "]")) + " -> " + groups.Count;
}
static void Main() {
int n = 8;
int[][] edges = { new[] {0, 1}, new[] {1, 2}, new[] {3, 4}, new[] {5, 6}, new[] {6, 7}, new[] {7, 5} };
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]);
}
Console.WriteLine("components of 8 vertices: " + Shown(Components(n, u => graph[u])));
int[,] isConnected = { {1, 0, 0, 1, 0}, // Number of Provinces hands over a matrix
{0, 1, 1, 0, 0},
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 0},
{0, 0, 0, 0, 1} };
var provinces = Components(5, u => Enumerable.Range(0, 5).Where(v => v != u && isConnected[u, v] == 1));
Console.WriteLine("provinces from the matrix: " + Shown(provinces));
}
}
// components of 8 vertices: [0 1 2] [3 4] [5 6 7] -> 3
// provinces from the matrix: [0 3] [1 2] [4] -> 3package main
import (
"fmt"
"sort"
"strconv"
"strings"
)
func components(n int, neighbours func(int) []int) [][]int { // one search from every vertex no search has reached
seen := make([]bool, n)
groups := [][]int{}
for s := 0; s < n; s++ {
if seen[s] {
continue
}
seen[s] = true
group, stack := []int{}, []int{s}
for len(stack) > 0 {
u := stack[len(stack)-1]
stack = stack[:len(stack)-1]
group = append(group, u)
for _, v := range neighbours(u) {
if !seen[v] {
seen[v] = true
stack = append(stack, v)
}
}
}
sort.Ints(group)
groups = append(groups, group)
}
return groups
}
func shown(groups [][]int) string {
parts := []string{}
for _, g := range groups {
nums := []string{}
for _, v := range g {
nums = append(nums, strconv.Itoa(v))
}
parts = append(parts, "["+strings.Join(nums, " ")+"]")
}
return strings.Join(parts, " ") + " -> " + strconv.Itoa(len(groups))
}
func main() {
n := 8
edges := [][2]int{{0, 1}, {1, 2}, {3, 4}, {5, 6}, {6, 7}, {7, 5}}
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])
}
fmt.Println("components of 8 vertices: " + shown(components(n, func(u int) []int { return graph[u] })))
isConnected := [][]int{ // Number of Provinces hands over a matrix
{1, 0, 0, 1, 0},
{0, 1, 1, 0, 0},
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 0},
{0, 0, 0, 0, 1},
}
provinces := components(5, func(u int) []int {
out := []int{}
for v := 0; v < 5; v++ {
if v != u && isConnected[u][v] == 1 {
out = append(out, v)
}
}
return out
})
fmt.Println("provinces from the matrix: " + shown(provinces))
}
// components of 8 vertices: [0 1 2] [3 4] [5 6 7] -> 3
// provinces from the matrix: [0 3] [1 2] [4] -> 3Three searches for 8 vertices: from 0, finding 1 and 2; from 3, finding 4; from 5, finding 6 and 7. Every other vertex was already marked when the loop got to it. Number of Provinces hands its graph over as a matrix, so a vertex's neighbours come from reading its row: the same loop, in O(n²), which is also the size of the matrix it's given. Number of Connected Components in an Undirected Graph hands over edges: build the lists first, as in Introduction to Graphs.
Islands and flood fill
A grid needs no lists: a cell's neighbours come from four moves, kept when they stay inside the grid and land on the right kind of cell. Counting islands is the same loop over the cells: every land cell no search has reached starts a new island. Flood fill is one search from one cell, colouring as it goes:
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
grid = ["11001",
"10011",
"00100",
"11101"]
R, C = len(grid), len(grid[0])
seen = [[False] * C for _ in range(R)]
sizes = []
for r in range(R):
for c in range(C):
if grid[r][c] == "1" and not seen[r][c]: # land no search has reached: a new island
seen[r][c], stack, size = True, [(r, c)], 0
while stack:
cr, cc = stack.pop()
size += 1
for dr, dc in DIRS:
nr, nc = cr + dr, cc + dc
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "1" and not seen[nr][nc]:
seen[nr][nc] = True
stack.append((nr, nc))
sizes.append(size)
print("islands:", len(sizes), "of sizes", " ".join(map(str, sizes)))
image = [[3, 3, 1],
[3, 1, 1],
[3, 3, 2]]
sr, sc, colour = 2, 0, 7
old = image[sr][sc] # the new colour is the mark, so it must differ from the old
image[sr][sc] = colour
stack = [(sr, sc)]
while stack:
r, c = stack.pop()
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < 3 and 0 <= nc < 3 and image[nr][nc] == old:
image[nr][nc] = colour
stack.append((nr, nc))
print("flood fill from (2,0) with 7:")
for row in image:
print(" ".join(map(str, row)))
# islands: 4 of sizes 3 3 4 1
# flood fill from (2,0) with 7:
# 7 7 1
# 7 1 1
# 7 7 2import java.util.*;
public class Main {
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public static void main(String[] args) {
String[] grid = {"11001",
"10011",
"00100",
"11101"};
int R = grid.length, C = grid[0].length();
boolean[][] seen = new boolean[R][C];
List<Integer> sizes = new ArrayList<>();
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r].charAt(c) != '1' || seen[r][c]) continue; // land no search has reached: a new island
seen[r][c] = true;
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[] {r, c});
int size = 0;
while (!stack.isEmpty()) {
int[] cell = stack.pop();
size++;
for (int[] d : DIRS) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr].charAt(nc) == '1' && !seen[nr][nc]) {
seen[nr][nc] = true;
stack.push(new int[] {nr, nc});
}
}
}
sizes.add(size);
}
}
StringJoiner s = new StringJoiner(" ");
for (int size : sizes) s.add(String.valueOf(size));
System.out.println("islands: " + sizes.size() + " of sizes " + s);
int[][] image = {{3, 3, 1},
{3, 1, 1},
{3, 3, 2}};
int sr = 2, sc = 0, colour = 7;
int old = image[sr][sc]; // the new colour is the mark, so it must differ from the old
image[sr][sc] = colour;
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[] {sr, sc});
while (!stack.isEmpty()) {
int[] cell = stack.pop();
for (int[] d : DIRS) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3 && image[nr][nc] == old) {
image[nr][nc] = colour;
stack.push(new int[] {nr, nc});
}
}
}
System.out.println("flood fill from (2,0) with 7:");
for (int[] row : image) {
StringJoiner line = new StringJoiner(" ");
for (int v : row) line.add(String.valueOf(v));
System.out.println(line);
}
}
}
// islands: 4 of sizes 3 3 4 1
// flood fill from (2,0) with 7:
// 7 7 1
// 7 1 1
// 7 7 2#include <bits/stdc++.h>
using namespace std;
const int DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int main() {
vector<string> grid = {"11001",
"10011",
"00100",
"11101"};
int R = grid.size(), C = grid[0].size();
vector<vector<bool>> seen(R, vector<bool>(C, false));
vector<int> sizes;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r][c] != '1' || seen[r][c]) continue; // land no search has reached: a new island
seen[r][c] = true;
vector<pair<int, int>> stack = {{r, c}};
int size = 0;
while (!stack.empty()) {
auto [cr, cc] = stack.back();
stack.pop_back();
size++;
for (auto& d : DIRS) {
int nr = cr + d[0], nc = cc + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == '1' && !seen[nr][nc]) {
seen[nr][nc] = true;
stack.push_back({nr, nc});
}
}
}
sizes.push_back(size);
}
}
cout << "islands: " << sizes.size() << " of sizes";
for (int size : sizes) cout << " " << size;
cout << "\n";
vector<vector<int>> image = {{3, 3, 1},
{3, 1, 1},
{3, 3, 2}};
int sr = 2, sc = 0, colour = 7;
int old = image[sr][sc]; // the new colour is the mark, so it must differ from the old
image[sr][sc] = colour;
vector<pair<int, int>> stack = {{sr, sc}};
while (!stack.empty()) {
auto [r, c] = stack.back();
stack.pop_back();
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3 && image[nr][nc] == old) {
image[nr][nc] = colour;
stack.push_back({nr, nc});
}
}
}
cout << "flood fill from (2,0) with 7:\n";
for (auto& row : image) cout << row[0] << " " << row[1] << " " << row[2] << "\n";
}
// islands: 4 of sizes 3 3 4 1
// flood fill from (2,0) with 7:
// 7 7 1
// 7 1 1
// 7 7 2const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const grid = ["11001",
"10011",
"00100",
"11101"];
const R = grid.length, C = grid[0].length;
const seen = Array.from({ length: R }, () => new Array(C).fill(false));
const sizes = [];
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (grid[r][c] !== "1" || seen[r][c]) continue; // land no search has reached: a new island
seen[r][c] = true;
const stack = [[r, c]];
let size = 0;
while (stack.length) {
const [cr, cc] = stack.pop();
size++;
for (const [dr, dc] of DIRS) {
const nr = cr + dr, nc = cc + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === "1" && !seen[nr][nc]) {
seen[nr][nc] = true;
stack.push([nr, nc]);
}
}
}
sizes.push(size);
}
}
console.log(`islands: ${sizes.length} of sizes ${sizes.join(" ")}`);
const image = [[3, 3, 1],
[3, 1, 1],
[3, 3, 2]];
const sr = 2, sc = 0, colour = 7;
const old = image[sr][sc]; // the new colour is the mark, so it must differ from the old
image[sr][sc] = colour;
const stack = [[sr, sc]];
while (stack.length) {
const [r, c] = stack.pop();
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3 && image[nr][nc] === old) {
image[nr][nc] = colour;
stack.push([nr, nc]);
}
}
}
console.log("flood fill from (2,0) with 7:");
for (const row of image) console.log(row.join(" "));
// islands: 4 of sizes 3 3 4 1
// flood fill from (2,0) with 7:
// 7 7 1
// 7 1 1
// 7 7 2const DIRS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const grid: string[] = ["11001",
"10011",
"00100",
"11101"];
const R = grid.length, C = grid[0].length;
const seen: boolean[][] = Array.from({ length: R }, () => new Array(C).fill(false));
const sizes: number[] = [];
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (grid[r][c] !== "1" || seen[r][c]) continue; // land no search has reached: a new island
seen[r][c] = true;
const stack: [number, number][] = [[r, c]];
let size = 0;
while (stack.length) {
const [cr, cc] = stack.pop()!;
size++;
for (const [dr, dc] of DIRS) {
const nr = cr + dr, nc = cc + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === "1" && !seen[nr][nc]) {
seen[nr][nc] = true;
stack.push([nr, nc]);
}
}
}
sizes.push(size);
}
}
console.log(`islands: ${sizes.length} of sizes ${sizes.join(" ")}`);
const image: number[][] = [[3, 3, 1],
[3, 1, 1],
[3, 3, 2]];
const sr = 2, sc = 0, colour = 7;
const old = image[sr][sc]; // the new colour is the mark, so it must differ from the old
image[sr][sc] = colour;
const stack: [number, number][] = [[sr, sc]];
while (stack.length) {
const [r, c] = stack.pop()!;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3 && image[nr][nc] === old) {
image[nr][nc] = colour;
stack.push([nr, nc]);
}
}
}
console.log("flood fill from (2,0) with 7:");
for (const row of image) console.log(row.join(" "));
// islands: 4 of sizes 3 3 4 1
// flood fill from (2,0) with 7:
// 7 7 1
// 7 1 1
// 7 7 2using System;
using System.Collections.Generic;
class Program {
static readonly int[][] Dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
static void Main() {
string[] grid = {"11001",
"10011",
"00100",
"11101"};
int R = grid.Length, C = grid[0].Length;
var seen = new bool[R, C];
var sizes = new List<int>();
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r][c] != '1' || seen[r, c]) continue; // land no search has reached: a new island
seen[r, c] = true;
var stack = new Stack<int[]>();
stack.Push(new[] {r, c});
int size = 0;
while (stack.Count > 0) {
int[] cell = stack.Pop();
size++;
foreach (int[] d in Dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == '1' && !seen[nr, nc]) {
seen[nr, nc] = true;
stack.Push(new[] {nr, nc});
}
}
}
sizes.Add(size);
}
}
Console.WriteLine($"islands: {sizes.Count} of sizes {string.Join(" ", sizes)}");
int[,] image = { {3, 3, 1},
{3, 1, 1},
{3, 3, 2} };
int sr = 2, sc = 0, colour = 7;
int old = image[sr, sc]; // the new colour is the mark, so it must differ from the old
image[sr, sc] = colour;
var todo = new Stack<int[]>();
todo.Push(new[] {sr, sc});
while (todo.Count > 0) {
int[] cell = todo.Pop();
foreach (int[] d in Dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3 && image[nr, nc] == old) {
image[nr, nc] = colour;
todo.Push(new[] {nr, nc});
}
}
}
Console.WriteLine("flood fill from (2,0) with 7:");
for (int r = 0; r < 3; r++) Console.WriteLine($"{image[r, 0]} {image[r, 1]} {image[r, 2]}");
}
}
// islands: 4 of sizes 3 3 4 1
// flood fill from (2,0) with 7:
// 7 7 1
// 7 1 1
// 7 7 2package main
import (
"fmt"
"strconv"
"strings"
)
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func main() {
grid := []string{
"11001",
"10011",
"00100",
"11101",
}
R, C := len(grid), len(grid[0])
seen := make([][]bool, R)
for i := range seen {
seen[i] = make([]bool, C)
}
sizes := []string{}
for r := 0; r < R; r++ {
for c := 0; c < C; c++ {
if grid[r][c] != '1' || seen[r][c] { // land no search has reached: a new island
continue
}
seen[r][c] = true
stack := [][2]int{{r, c}}
size := 0
for len(stack) > 0 {
cell := stack[len(stack)-1]
stack = stack[:len(stack)-1]
size++
for _, d := range dirs {
nr, nc := cell[0]+d[0], cell[1]+d[1]
if nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == '1' && !seen[nr][nc] {
seen[nr][nc] = true
stack = append(stack, [2]int{nr, nc})
}
}
}
sizes = append(sizes, strconv.Itoa(size))
}
}
fmt.Printf("islands: %d of sizes %s\n", len(sizes), strings.Join(sizes, " "))
image := [][]int{
{3, 3, 1},
{3, 1, 1},
{3, 3, 2},
}
sr, sc, colour := 2, 0, 7
old := image[sr][sc] // the new colour is the mark, so it must differ from the old
image[sr][sc] = colour
stack := [][2]int{{sr, sc}}
for len(stack) > 0 {
cell := stack[len(stack)-1]
stack = stack[:len(stack)-1]
for _, d := range dirs {
nr, nc := cell[0]+d[0], cell[1]+d[1]
if nr >= 0 && nr < 3 && nc >= 0 && nc < 3 && image[nr][nc] == old {
image[nr][nc] = colour
stack = append(stack, [2]int{nr, nc})
}
}
}
fmt.Println("flood fill from (2,0) with 7:")
for _, row := range image {
fmt.Printf("%d %d %d\n", row[0], row[1], row[2])
}
}
// islands: 4 of sizes 3 3 4 1
// flood fill from (2,0) with 7:
// 7 7 1
// 7 1 1
// 7 7 2Four islands of 3, 3, 4 and 1 cells, found in reading order. The fill turned the five 3s joined to (2,0) into 7s and touched nothing else. It uses the new colour as its mark, which only works when the new colour differs from the old one: if they're the same, every cell it colours still looks uncoloured and the fill never ends, so check for that first.
Some problems move in eight directions, the diagonals too: the same search with eight moves. Marking the grid itself, by overwriting land with water, saves the marks' memory but destroys the input; when the caller still needs the grid, keep a separate set of marks.
Start from the border
Some questions are about what can't be reached: land that can't walk off the grid (Number of Enclaves), regions of O that no O on the border can reach (Surrounded Regions). Asking every land cell whether it reaches the border repeats the same work over and over. Turn it around: start one search from every border cell at once, mark everything it reaches, and the answer is what's left unmarked. Pacific Atlantic Water Flow does that twice, once from each ocean, walking uphill, because water runs downhill to the sea:
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
def search(R, C, starts, can_step): # one search from many cells at once
reached = [[False] * C for _ in range(R)]
stack = list(starts)
for r, c in stack:
reached[r][c] = True
while stack:
r, c = stack.pop()
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and not reached[nr][nc] and can_step(r, c, nr, nc):
reached[nr][nc] = True
stack.append((nr, nc))
return reached
grid = [[0, 0, 0, 0, 0],
[1, 0, 1, 1, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 1, 1]]
R, C = len(grid), len(grid[0])
border = [(r, c) for r in range(R) for c in range(C) if grid[r][c] == 1 and (r in (0, R - 1) or c in (0, C - 1))]
off = search(R, C, border, lambda r, c, nr, nc: grid[nr][nc] == 1)
print("land that can't walk off the grid:", sum(grid[r][c] == 1 and not off[r][c] for r in range(R) for c in range(C)))
heights = [[1, 2, 3],
[8, 9, 4],
[7, 6, 5]]
R, C = 3, 3
uphill = lambda r, c, nr, nc: heights[nr][nc] >= heights[r][c] # water runs down, so search up from the sea
pacific = search(R, C, [(0, c) for c in range(C)] + [(r, 0) for r in range(1, R)], uphill)
atlantic = search(R, C, [(R - 1, c) for c in range(C)] + [(r, C - 1) for r in range(R - 1)], uphill)
both = [f"({r},{c})" for r in range(R) for c in range(C) if pacific[r][c] and atlantic[r][c]]
print("water reaches both oceans from:", " ".join(both))
# land that can't walk off the grid: 4
# water reaches both oceans from: (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)import java.util.*;
public class Main {
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
interface Step {
boolean ok(int r, int c, int nr, int nc);
}
static boolean[][] search(int R, int C, List<int[]> starts, Step canStep) { // one search from many cells at once
boolean[][] reached = new boolean[R][C];
Deque<int[]> stack = new ArrayDeque<>();
for (int[] s : starts) {
reached[s[0]][s[1]] = true;
stack.push(s);
}
while (!stack.isEmpty()) {
int[] cell = stack.pop();
for (int[] d : DIRS) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !reached[nr][nc] && canStep.ok(cell[0], cell[1], nr, nc)) {
reached[nr][nc] = true;
stack.push(new int[] {nr, nc});
}
}
}
return reached;
}
public static void main(String[] args) {
int[][] grid = {{0, 0, 0, 0, 0},
{1, 0, 1, 1, 0},
{0, 1, 1, 0, 0},
{0, 0, 0, 1, 1}};
int R = grid.length, C = grid[0].length;
List<int[]> border = new ArrayList<>();
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (grid[r][c] == 1 && (r == 0 || r == R - 1 || c == 0 || c == C - 1)) border.add(new int[] {r, c});
boolean[][] off = search(R, C, border, (r, c, nr, nc) -> grid[nr][nc] == 1);
int enclosed = 0;
for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) if (grid[r][c] == 1 && !off[r][c]) enclosed++;
System.out.println("land that can't walk off the grid: " + enclosed);
int[][] heights = {{1, 2, 3},
{8, 9, 4},
{7, 6, 5}};
Step uphill = (r, c, nr, nc) -> heights[nr][nc] >= heights[r][c]; // water runs down, so search up from the sea
List<int[]> pacificSide = new ArrayList<>(), atlanticSide = new ArrayList<>();
for (int c = 0; c < 3; c++) pacificSide.add(new int[] {0, c});
for (int r = 1; r < 3; r++) pacificSide.add(new int[] {r, 0});
for (int c = 0; c < 3; c++) atlanticSide.add(new int[] {2, c});
for (int r = 0; r < 2; r++) atlanticSide.add(new int[] {r, 2});
boolean[][] pacific = search(3, 3, pacificSide, uphill), atlantic = search(3, 3, atlanticSide, uphill);
StringJoiner both = new StringJoiner(" ");
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++)
if (pacific[r][c] && atlantic[r][c]) both.add("(" + r + "," + c + ")");
System.out.println("water reaches both oceans from: " + both);
}
}
// land that can't walk off the grid: 4
// water reaches both oceans from: (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)#include <bits/stdc++.h>
using namespace std;
const int DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<bool>> search(int R, int C, vector<pair<int, int>> starts,
function<bool(int, int, int, int)> canStep) { // one search from many cells at once
vector<vector<bool>> reached(R, vector<bool>(C, false));
for (auto [r, c] : starts) reached[r][c] = true;
vector<pair<int, int>> stack = starts;
while (!stack.empty()) {
auto [r, c] = stack.back();
stack.pop_back();
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !reached[nr][nc] && canStep(r, c, nr, nc)) {
reached[nr][nc] = true;
stack.push_back({nr, nc});
}
}
}
return reached;
}
int main() {
vector<vector<int>> grid = {{0, 0, 0, 0, 0},
{1, 0, 1, 1, 0},
{0, 1, 1, 0, 0},
{0, 0, 0, 1, 1}};
int R = grid.size(), C = grid[0].size();
vector<pair<int, int>> border;
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (grid[r][c] == 1 && (r == 0 || r == R - 1 || c == 0 || c == C - 1)) border.push_back({r, c});
auto off = search(R, C, border, [&](int r, int c, int nr, int nc) { return grid[nr][nc] == 1; });
int enclosed = 0;
for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) if (grid[r][c] == 1 && !off[r][c]) enclosed++;
cout << "land that can't walk off the grid: " << enclosed << "\n";
vector<vector<int>> heights = {{1, 2, 3},
{8, 9, 4},
{7, 6, 5}};
auto uphill = [&](int r, int c, int nr, int nc) { return heights[nr][nc] >= heights[r][c]; }; // search up from the sea
vector<pair<int, int>> pacificSide, atlanticSide;
for (int c = 0; c < 3; c++) pacificSide.push_back({0, c});
for (int r = 1; r < 3; r++) pacificSide.push_back({r, 0});
for (int c = 0; c < 3; c++) atlanticSide.push_back({2, c});
for (int r = 0; r < 2; r++) atlanticSide.push_back({r, 2});
auto pacific = search(3, 3, pacificSide, uphill), atlantic = search(3, 3, atlanticSide, uphill);
cout << "water reaches both oceans from:";
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++)
if (pacific[r][c] && atlantic[r][c]) cout << " (" << r << "," << c << ")";
cout << "\n";
}
// land that can't walk off the grid: 4
// water reaches both oceans from: (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function search(R, C, starts, canStep) { // one search from many cells at once
const reached = Array.from({ length: R }, () => new Array(C).fill(false));
for (const [r, c] of starts) reached[r][c] = true;
const stack = [...starts];
while (stack.length) {
const [r, c] = stack.pop();
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !reached[nr][nc] && canStep(r, c, nr, nc)) {
reached[nr][nc] = true;
stack.push([nr, nc]);
}
}
}
return reached;
}
const grid = [[0, 0, 0, 0, 0],
[1, 0, 1, 1, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 1, 1]];
let R = grid.length, C = grid[0].length;
const border = [];
for (let r = 0; r < R; r++)
for (let c = 0; c < C; c++)
if (grid[r][c] === 1 && (r === 0 || r === R - 1 || c === 0 || c === C - 1)) border.push([r, c]);
const off = search(R, C, border, (r, c, nr, nc) => grid[nr][nc] === 1);
let enclosed = 0;
for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (grid[r][c] === 1 && !off[r][c]) enclosed++;
console.log(`land that can't walk off the grid: ${enclosed}`);
const heights = [[1, 2, 3],
[8, 9, 4],
[7, 6, 5]];
const uphill = (r, c, nr, nc) => heights[nr][nc] >= heights[r][c]; // water runs down, so search up from the sea
const pacific = search(3, 3, [[0, 0], [0, 1], [0, 2], [1, 0], [2, 0]], uphill);
const atlantic = search(3, 3, [[2, 0], [2, 1], [2, 2], [0, 2], [1, 2]], uphill);
const both = [];
for (let r = 0; r < 3; r++) for (let c = 0; c < 3; c++) if (pacific[r][c] && atlantic[r][c]) both.push(`(${r},${c})`);
console.log(`water reaches both oceans from: ${both.join(" ")}`);
// land that can't walk off the grid: 4
// water reaches both oceans from: (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)const DIRS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
type Step = (r: number, c: number, nr: number, nc: number) => boolean;
function search(R: number, C: number, starts: [number, number][], canStep: Step): boolean[][] {
const reached: boolean[][] = Array.from({ length: R }, () => new Array(C).fill(false)); // many starts at once
for (const [r, c] of starts) reached[r][c] = true;
const stack: [number, number][] = [...starts];
while (stack.length) {
const [r, c] = stack.pop()!;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !reached[nr][nc] && canStep(r, c, nr, nc)) {
reached[nr][nc] = true;
stack.push([nr, nc]);
}
}
}
return reached;
}
const grid: number[][] = [[0, 0, 0, 0, 0],
[1, 0, 1, 1, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 1, 1]];
const R = grid.length, C = grid[0].length;
const border: [number, number][] = [];
for (let r = 0; r < R; r++)
for (let c = 0; c < C; c++)
if (grid[r][c] === 1 && (r === 0 || r === R - 1 || c === 0 || c === C - 1)) border.push([r, c]);
const off = search(R, C, border, (r, c, nr, nc) => grid[nr][nc] === 1);
let enclosed = 0;
for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (grid[r][c] === 1 && !off[r][c]) enclosed++;
console.log(`land that can't walk off the grid: ${enclosed}`);
const heights: number[][] = [[1, 2, 3],
[8, 9, 4],
[7, 6, 5]];
const uphill: Step = (r, c, nr, nc) => heights[nr][nc] >= heights[r][c]; // water runs down, so search up from the sea
const pacific = search(3, 3, [[0, 0], [0, 1], [0, 2], [1, 0], [2, 0]], uphill);
const atlantic = search(3, 3, [[2, 0], [2, 1], [2, 2], [0, 2], [1, 2]], uphill);
const both: string[] = [];
for (let r = 0; r < 3; r++) for (let c = 0; c < 3; c++) if (pacific[r][c] && atlantic[r][c]) both.push(`(${r},${c})`);
console.log(`water reaches both oceans from: ${both.join(" ")}`);
// land that can't walk off the grid: 4
// water reaches both oceans from: (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)using System;
using System.Collections.Generic;
class Program {
static readonly int[][] Dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
static bool[,] Search(int R, int C, List<int[]> starts, Func<int, int, int, int, bool> canStep) {
var reached = new bool[R, C]; // one search from many cells at once
var stack = new Stack<int[]>();
foreach (int[] s in starts) {
reached[s[0], s[1]] = true;
stack.Push(s);
}
while (stack.Count > 0) {
int[] cell = stack.Pop();
foreach (int[] d in Dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !reached[nr, nc] && canStep(cell[0], cell[1], nr, nc)) {
reached[nr, nc] = true;
stack.Push(new[] {nr, nc});
}
}
}
return reached;
}
static void Main() {
int[,] grid = { {0, 0, 0, 0, 0},
{1, 0, 1, 1, 0},
{0, 1, 1, 0, 0},
{0, 0, 0, 1, 1} };
int R = grid.GetLength(0), C = grid.GetLength(1);
var border = new List<int[]>();
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (grid[r, c] == 1 && (r == 0 || r == R - 1 || c == 0 || c == C - 1)) border.Add(new[] {r, c});
var off = Search(R, C, border, (r, c, nr, nc) => grid[nr, nc] == 1);
int enclosed = 0;
for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) if (grid[r, c] == 1 && !off[r, c]) enclosed++;
Console.WriteLine($"land that can't walk off the grid: {enclosed}");
int[,] heights = { {1, 2, 3},
{8, 9, 4},
{7, 6, 5} };
Func<int, int, int, int, bool> uphill = (r, c, nr, nc) => heights[nr, nc] >= heights[r, c]; // search up from the sea
var pacificSide = new List<int[]> { new[] {0, 0}, new[] {0, 1}, new[] {0, 2}, new[] {1, 0}, new[] {2, 0} };
var atlanticSide = new List<int[]> { new[] {2, 0}, new[] {2, 1}, new[] {2, 2}, new[] {0, 2}, new[] {1, 2} };
var pacific = Search(3, 3, pacificSide, uphill);
var atlantic = Search(3, 3, atlanticSide, uphill);
var both = new List<string>();
for (int r = 0; r < 3; r++) for (int c = 0; c < 3; c++) if (pacific[r, c] && atlantic[r, c]) both.Add($"({r},{c})");
Console.WriteLine($"water reaches both oceans from: {string.Join(" ", both)}");
}
}
// land that can't walk off the grid: 4
// water reaches both oceans from: (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)package main
import (
"fmt"
"strings"
)
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func search(R, C int, starts [][2]int, canStep func(r, c, nr, nc int) bool) [][]bool { // one search, many starts
reached := make([][]bool, R)
for i := range reached {
reached[i] = make([]bool, C)
}
stack := append([][2]int{}, starts...)
for _, s := range starts {
reached[s[0]][s[1]] = true
}
for len(stack) > 0 {
cell := stack[len(stack)-1]
stack = stack[:len(stack)-1]
for _, d := range dirs {
nr, nc := cell[0]+d[0], cell[1]+d[1]
if nr >= 0 && nr < R && nc >= 0 && nc < C && !reached[nr][nc] && canStep(cell[0], cell[1], nr, nc) {
reached[nr][nc] = true
stack = append(stack, [2]int{nr, nc})
}
}
}
return reached
}
func main() {
grid := [][]int{
{0, 0, 0, 0, 0},
{1, 0, 1, 1, 0},
{0, 1, 1, 0, 0},
{0, 0, 0, 1, 1},
}
R, C := len(grid), len(grid[0])
border := [][2]int{}
for r := 0; r < R; r++ {
for c := 0; c < C; c++ {
if grid[r][c] == 1 && (r == 0 || r == R-1 || c == 0 || c == C-1) {
border = append(border, [2]int{r, c})
}
}
}
off := search(R, C, border, func(r, c, nr, nc int) bool { return grid[nr][nc] == 1 })
enclosed := 0
for r := 0; r < R; r++ {
for c := 0; c < C; c++ {
if grid[r][c] == 1 && !off[r][c] {
enclosed++
}
}
}
fmt.Println("land that can't walk off the grid:", enclosed)
heights := [][]int{
{1, 2, 3},
{8, 9, 4},
{7, 6, 5},
}
uphill := func(r, c, nr, nc int) bool { return heights[nr][nc] >= heights[r][c] } // search up from the sea
pacific := search(3, 3, [][2]int{{0, 0}, {0, 1}, {0, 2}, {1, 0}, {2, 0}}, uphill)
atlantic := search(3, 3, [][2]int{{2, 0}, {2, 1}, {2, 2}, {0, 2}, {1, 2}}, uphill)
both := []string{}
for r := 0; r < 3; r++ {
for c := 0; c < 3; c++ {
if pacific[r][c] && atlantic[r][c] {
both = append(both, fmt.Sprintf("(%d,%d)", r, c))
}
}
}
fmt.Println("water reaches both oceans from: " + strings.Join(both, " "))
}
// land that can't walk off the grid: 4
// water reaches both oceans from: (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)Four land cells can't reach the border: the group of (1,2), (1,3), (2,1) and (2,2). For the heights, every cell can drain to the Pacific (the top and the left), and seven can drain to the Atlantic as well; water from (0,0) and (0,1) can't climb the higher cells around them to reach the bottom or the right. Each search is still O(R × C): all its starts just go on the waiting list together.
Telling islands apart by shape
Number of Distinct Islands asks how many different shapes there are. A shape is an island wherever it sits, so give each island a key: subtract its smallest row and column from every cell, so it starts at (0, 0), and sort the cells. Number of Distinct Islands II also counts a shape turned or flipped as the same one, so try all eight ways to turn or flip it (swap the row and column or not, and negate either one), make each one's key, and keep the smallest:
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
grid = ["11000",
"10001",
"00011",
"01000",
"11010"]
R, C = len(grid), len(grid[0])
seen = [[False] * C for _ in range(R)]
islands = []
for r in range(R):
for c in range(C):
if grid[r][c] == "1" and not seen[r][c]:
seen[r][c], stack, cells = True, [(r, c)], []
while stack:
cr, cc = stack.pop()
cells.append((cr, cc))
for dr, dc in DIRS:
nr, nc = cr + dr, cc + dc
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "1" and not seen[nr][nc]:
seen[nr][nc] = True
stack.append((nr, nc))
islands.append(cells)
def key(cells): # a shape wherever it sits: its cells from (0, 0), sorted, as text
r0 = min(r for r, _ in cells)
c0 = min(c for _, c in cells)
return ";".join(f"{r},{c}" for r, c in sorted((r - r0, c - c0) for r, c in cells))
def canonical(cells): # the smallest key of its 8 rotations and reflections
keys = []
for a, b in ((1, 1), (1, -1), (-1, 1), (-1, -1)):
keys.append(key([(a * r, b * c) for r, c in cells]))
keys.append(key([(a * c, b * r) for r, c in cells]))
return min(keys)
print("islands:", len(islands))
print("shapes, only moved:", len({key(cells) for cells in islands}))
print("shapes, also turned or flipped:", len({canonical(cells) for cells in islands}))
# islands: 4
# shapes, only moved: 3
# shapes, also turned or flipped: 2import java.util.*;
public class Main {
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static String key(List<int[]> cells) { // a shape wherever it sits: its cells from (0, 0), sorted, as text
int r0 = Integer.MAX_VALUE, c0 = Integer.MAX_VALUE;
for (int[] p : cells) {
r0 = Math.min(r0, p[0]);
c0 = Math.min(c0, p[1]);
}
List<int[]> moved = new ArrayList<>();
for (int[] p : cells) moved.add(new int[] {p[0] - r0, p[1] - c0});
moved.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
StringJoiner s = new StringJoiner(";");
for (int[] p : moved) s.add(p[0] + "," + p[1]);
return s.toString();
}
static String canonical(List<int[]> cells) { // the smallest key of its 8 rotations and reflections
String best = null;
int[][] signs = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
for (int[] s : signs) {
for (boolean swap : new boolean[] {false, true}) {
List<int[]> turned = new ArrayList<>();
for (int[] p : cells) turned.add(swap ? new int[] {s[0] * p[1], s[1] * p[0]} : new int[] {s[0] * p[0], s[1] * p[1]});
String k = key(turned);
if (best == null || k.compareTo(best) < 0) best = k;
}
}
return best;
}
public static void main(String[] args) {
String[] grid = {"11000",
"10001",
"00011",
"01000",
"11010"};
int R = grid.length, C = grid[0].length();
boolean[][] seen = new boolean[R][C];
List<List<int[]>> islands = new ArrayList<>();
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r].charAt(c) != '1' || seen[r][c]) continue;
seen[r][c] = true;
List<int[]> cells = new ArrayList<>();
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[] {r, c});
while (!stack.isEmpty()) {
int[] cell = stack.pop();
cells.add(cell);
for (int[] d : DIRS) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr].charAt(nc) == '1' && !seen[nr][nc]) {
seen[nr][nc] = true;
stack.push(new int[] {nr, nc});
}
}
}
islands.add(cells);
}
}
Set<String> moved = new HashSet<>(), turned = new HashSet<>();
for (List<int[]> cells : islands) {
moved.add(key(cells));
turned.add(canonical(cells));
}
System.out.println("islands: " + islands.size());
System.out.println("shapes, only moved: " + moved.size());
System.out.println("shapes, also turned or flipped: " + turned.size());
}
}
// islands: 4
// shapes, only moved: 3
// shapes, also turned or flipped: 2#include <bits/stdc++.h>
using namespace std;
const int DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
string key(vector<pair<int, int>> cells) { // a shape wherever it sits: its cells from (0, 0), sorted, as text
int r0 = INT_MAX, c0 = INT_MAX;
for (auto [r, c] : cells) {
r0 = min(r0, r);
c0 = min(c0, c);
}
for (auto& p : cells) p = {p.first - r0, p.second - c0};
sort(cells.begin(), cells.end());
string s;
for (size_t i = 0; i < cells.size(); i++) s += (i ? ";" : "") + to_string(cells[i].first) + "," + to_string(cells[i].second);
return s;
}
string canonical(const vector<pair<int, int>>& cells) { // the smallest key of its 8 rotations and reflections
string best;
int signs[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
for (auto& s : signs) {
for (bool swap : {false, true}) {
vector<pair<int, int>> turned;
for (auto [r, c] : cells) turned.push_back(swap ? make_pair(s[0] * c, s[1] * r) : make_pair(s[0] * r, s[1] * c));
string k = key(turned);
if (best.empty() || k < best) best = k;
}
}
return best;
}
int main() {
vector<string> grid = {"11000",
"10001",
"00011",
"01000",
"11010"};
int R = grid.size(), C = grid[0].size();
vector<vector<bool>> seen(R, vector<bool>(C, false));
vector<vector<pair<int, int>>> islands;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r][c] != '1' || seen[r][c]) continue;
seen[r][c] = true;
vector<pair<int, int>> cells, stack = {{r, c}};
while (!stack.empty()) {
auto [cr, cc] = stack.back();
stack.pop_back();
cells.push_back({cr, cc});
for (auto& d : DIRS) {
int nr = cr + d[0], nc = cc + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == '1' && !seen[nr][nc]) {
seen[nr][nc] = true;
stack.push_back({nr, nc});
}
}
}
islands.push_back(cells);
}
}
set<string> moved, turned;
for (auto& cells : islands) {
moved.insert(key(cells));
turned.insert(canonical(cells));
}
cout << "islands: " << islands.size() << "\n";
cout << "shapes, only moved: " << moved.size() << "\n";
cout << "shapes, also turned or flipped: " << turned.size() << "\n";
}
// islands: 4
// shapes, only moved: 3
// shapes, also turned or flipped: 2const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const grid = ["11000",
"10001",
"00011",
"01000",
"11010"];
const R = grid.length, C = grid[0].length;
const seen = Array.from({ length: R }, () => new Array(C).fill(false));
const islands = [];
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (grid[r][c] !== "1" || seen[r][c]) continue;
seen[r][c] = true;
const cells = [], stack = [[r, c]];
while (stack.length) {
const [cr, cc] = stack.pop();
cells.push([cr, cc]);
for (const [dr, dc] of DIRS) {
const nr = cr + dr, nc = cc + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === "1" && !seen[nr][nc]) {
seen[nr][nc] = true;
stack.push([nr, nc]);
}
}
}
islands.push(cells);
}
}
function key(cells) { // a shape wherever it sits: its cells from (0, 0), sorted, as text
const r0 = Math.min(...cells.map(([r]) => r)), c0 = Math.min(...cells.map(([, c]) => c));
return cells.map(([r, c]) => [r - r0, c - c0])
.sort((a, b) => a[0] - b[0] || a[1] - b[1])
.map(([r, c]) => `${r},${c}`).join(";");
}
function canonical(cells) { // the smallest key of its 8 rotations and reflections
const keys = [];
for (const [a, b] of [[1, 1], [1, -1], [-1, 1], [-1, -1]]) {
keys.push(key(cells.map(([r, c]) => [a * r, b * c])));
keys.push(key(cells.map(([r, c]) => [a * c, b * r])));
}
return keys.reduce((x, y) => (y < x ? y : x));
}
console.log(`islands: ${islands.length}`);
console.log(`shapes, only moved: ${new Set(islands.map(key)).size}`);
console.log(`shapes, also turned or flipped: ${new Set(islands.map(canonical)).size}`);
// islands: 4
// shapes, only moved: 3
// shapes, also turned or flipped: 2const DIRS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const grid: string[] = ["11000",
"10001",
"00011",
"01000",
"11010"];
const R = grid.length, C = grid[0].length;
const seen: boolean[][] = Array.from({ length: R }, () => new Array(C).fill(false));
const islands: [number, number][][] = [];
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (grid[r][c] !== "1" || seen[r][c]) continue;
seen[r][c] = true;
const cells: [number, number][] = [], stack: [number, number][] = [[r, c]];
while (stack.length) {
const [cr, cc] = stack.pop()!;
cells.push([cr, cc]);
for (const [dr, dc] of DIRS) {
const nr = cr + dr, nc = cc + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === "1" && !seen[nr][nc]) {
seen[nr][nc] = true;
stack.push([nr, nc]);
}
}
}
islands.push(cells);
}
}
function key(cells: [number, number][]): string { // a shape wherever it sits: its cells from (0, 0), sorted, as text
const r0 = Math.min(...cells.map(([r]) => r)), c0 = Math.min(...cells.map(([, c]) => c));
return cells.map(([r, c]): [number, number] => [r - r0, c - c0])
.sort((a, b) => a[0] - b[0] || a[1] - b[1])
.map(([r, c]) => `${r},${c}`).join(";");
}
function canonical(cells: [number, number][]): string { // the smallest key of its 8 rotations and reflections
const keys: string[] = [];
for (const [a, b] of [[1, 1], [1, -1], [-1, 1], [-1, -1]]) {
keys.push(key(cells.map(([r, c]): [number, number] => [a * r, b * c])));
keys.push(key(cells.map(([r, c]): [number, number] => [a * c, b * r])));
}
return keys.reduce((x, y) => (y < x ? y : x));
}
console.log(`islands: ${islands.length}`);
console.log(`shapes, only moved: ${new Set(islands.map(key)).size}`);
console.log(`shapes, also turned or flipped: ${new Set(islands.map(canonical)).size}`);
// islands: 4
// shapes, only moved: 3
// shapes, also turned or flipped: 2using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static readonly int[][] Dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
static string Key(List<int[]> cells) { // a shape wherever it sits: its cells from (0, 0), sorted, as text
int r0 = cells.Min(p => p[0]), c0 = cells.Min(p => p[1]);
var moved = cells.Select(p => new[] {p[0] - r0, p[1] - c0}).OrderBy(p => p[0]).ThenBy(p => p[1]);
return string.Join(";", moved.Select(p => p[0] + "," + p[1]));
}
static string Canonical(List<int[]> cells) { // the smallest key of its 8 rotations and reflections
var keys = new List<string>();
foreach (int[] s in new[] { new[] {1, 1}, new[] {1, -1}, new[] {-1, 1}, new[] {-1, -1} }) {
keys.Add(Key(cells.Select(p => new[] {s[0] * p[0], s[1] * p[1]}).ToList()));
keys.Add(Key(cells.Select(p => new[] {s[0] * p[1], s[1] * p[0]}).ToList()));
}
return keys.OrderBy(k => k, StringComparer.Ordinal).First();
}
static void Main() {
string[] grid = {"11000",
"10001",
"00011",
"01000",
"11010"};
int R = grid.Length, C = grid[0].Length;
var seen = new bool[R, C];
var islands = new List<List<int[]>>();
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r][c] != '1' || seen[r, c]) continue;
seen[r, c] = true;
var cells = new List<int[]>();
var stack = new Stack<int[]>();
stack.Push(new[] {r, c});
while (stack.Count > 0) {
int[] cell = stack.Pop();
cells.Add(cell);
foreach (int[] d in Dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == '1' && !seen[nr, nc]) {
seen[nr, nc] = true;
stack.Push(new[] {nr, nc});
}
}
}
islands.Add(cells);
}
}
Console.WriteLine($"islands: {islands.Count}");
Console.WriteLine($"shapes, only moved: {islands.Select(Key).Distinct().Count()}");
Console.WriteLine($"shapes, also turned or flipped: {islands.Select(Canonical).Distinct().Count()}");
}
}
// islands: 4
// shapes, only moved: 3
// shapes, also turned or flipped: 2package main
import (
"fmt"
"sort"
"strconv"
"strings"
)
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func key(cells [][2]int) string { // a shape wherever it sits: its cells from (0, 0), sorted, as text
r0, c0 := cells[0][0], cells[0][1]
for _, p := range cells {
if p[0] < r0 {
r0 = p[0]
}
if p[1] < c0 {
c0 = p[1]
}
}
moved := make([][2]int, len(cells))
for i, p := range cells {
moved[i] = [2]int{p[0] - r0, p[1] - c0}
}
sort.Slice(moved, func(i, j int) bool {
if moved[i][0] != moved[j][0] {
return moved[i][0] < moved[j][0]
}
return moved[i][1] < moved[j][1]
})
parts := make([]string, len(moved))
for i, p := range moved {
parts[i] = strconv.Itoa(p[0]) + "," + strconv.Itoa(p[1])
}
return strings.Join(parts, ";")
}
func canonical(cells [][2]int) string { // the smallest key of its 8 rotations and reflections
best := ""
for _, s := range [][2]int{{1, 1}, {1, -1}, {-1, 1}, {-1, -1}} {
for _, swap := range []bool{false, true} {
turned := make([][2]int, len(cells))
for i, p := range cells {
if swap {
turned[i] = [2]int{s[0] * p[1], s[1] * p[0]}
} else {
turned[i] = [2]int{s[0] * p[0], s[1] * p[1]}
}
}
if k := key(turned); best == "" || k < best {
best = k
}
}
}
return best
}
func main() {
grid := []string{
"11000",
"10001",
"00011",
"01000",
"11010",
}
R, C := len(grid), len(grid[0])
seen := make([][]bool, R)
for i := range seen {
seen[i] = make([]bool, C)
}
islands := [][][2]int{}
for r := 0; r < R; r++ {
for c := 0; c < C; c++ {
if grid[r][c] != '1' || seen[r][c] {
continue
}
seen[r][c] = true
cells, stack := [][2]int{}, [][2]int{{r, c}}
for len(stack) > 0 {
cell := stack[len(stack)-1]
stack = stack[:len(stack)-1]
cells = append(cells, cell)
for _, d := range dirs {
nr, nc := cell[0]+d[0], cell[1]+d[1]
if nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == '1' && !seen[nr][nc] {
seen[nr][nc] = true
stack = append(stack, [2]int{nr, nc})
}
}
}
islands = append(islands, cells)
}
}
moved, turned := map[string]bool{}, map[string]bool{}
for _, cells := range islands {
moved[key(cells)] = true
turned[canonical(cells)] = true
}
fmt.Println("islands:", len(islands))
fmt.Println("shapes, only moved:", len(moved))
fmt.Println("shapes, also turned or flipped:", len(turned))
}
// islands: 4
// shapes, only moved: 3
// shapes, also turned or flipped: 2Four islands. Moved only, they're three shapes: two of the three-cell L shapes point the same way and match. Turned or flipped, the third L matches them too, and only the single cell is left over: two shapes. Any rule that picks one of the eight keys the same way every time works; the smallest is just the simplest to write.
Which search to use
- The fewest steps (moves, flips, word changes) in a graph or grid where every step costs the same: BFS, every time.
- Everything reachable, every group, a fill, a yes-or-no about reaching: either. Pick the one you write fastest, and on big inputs use your own stack or a queue rather than recursion.
- Something about the path itself, like a cycle or the order vertices finish in: DFS, in Cycles, Bipartite Graphs and Topological Order and Bridges, Articulation Points and Strong Components.
- Steps with different costs: neither on its own; that's Weighted Shortest Paths: Dijkstra, Bellman-Ford and Floyd-Warshall.
Near misses: a tree's traversals in Tree Traversals: Depth-First and Breadth-First are these same two searches with no marks, because a tree has no cycle to come back around; backtracking, in Backtracking on Grids and Constraints, walks a grid like DFS but takes its mark back off on the way out, so a cell can be used again on another path.
Mistakes that look right
Two of these run below in every language. The others are just as common:
- Marking on the way out in BFS: a vertex goes in once for every neighbour that finds it first.
- DFS for the fewest steps: the first path it finds can be the long way round.
- A start that's never marked: a neighbour puts it back on the list, and it's visited twice.
- Counting groups with one search from vertex 0: everything not joined to 0 is missed.
- A recursive fill on a big grid: the stack runs out, as it did for four of the seven above.
- Flood fill with the same colour: nothing ever looks done, and it never ends.
- Overwriting the grid as the mark when the caller still needs the grid afterwards.
from collections import deque
R = C = 30
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
def pushes(mark_going_in): # a BFS over a 30 x 30 grid of land, counting what goes in
seen = [[False] * C for _ in range(R)]
queue, count = deque([(0, 0)]), 1
seen[0][0] = mark_going_in
while queue:
r, c = queue.popleft()
if not mark_going_in:
if seen[r][c]:
continue # the bug's cost: in once for every neighbour that saw it first
seen[r][c] = True
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and not seen[nr][nc]:
if mark_going_in:
seen[nr][nc] = True
queue.append((nr, nc))
count += 1
return count
print("marked going in: ", pushes(True), "pushes for", R * C, "cells")
print("marked coming out:", pushes(False), "pushes for", R * C, "cells")
n = 7
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (4, 6), (5, 6)]
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
def path_to(parent, v):
path = []
while v != -1:
path.append(v)
v = parent[v]
return path[::-1]
def shown(path):
edges_used = len(path) - 1
return " ".join(map(str, path)) + f" ({edges_used} {'edge' if edges_used == 1 else 'edges'})"
parent, seen = [-1] * n, [False] * n
def dfs(u):
seen[u] = True
for v in graph[u]:
if not seen[v]:
parent[v] = u # the edge the search first reached v by
dfs(v)
dfs(0)
print("DFS's path from 0 to 2:", shown(path_to(parent, 2)))
parent, seen = [-1] * n, [False] * n
seen[0], queue = True, deque([0])
while queue:
u = queue.popleft()
for v in graph[u]:
if not seen[v]:
seen[v], parent[v] = True, u
queue.append(v)
print("BFS's path from 0 to 2:", shown(path_to(parent, 2)))
# marked going in: 900 pushes for 900 cells
# marked coming out: 1741 pushes for 900 cells
# DFS's path from 0 to 2: 0 1 4 6 5 2 (5 edges)
# BFS's path from 0 to 2: 0 2 (1 edge)import java.util.*;
public class Main {
static final int R = 30, C = 30;
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static List<List<Integer>> graph = new ArrayList<>();
static int[] parent;
static boolean[] seen;
static int pushes(boolean markGoingIn) { // a BFS over a 30 x 30 grid of land, counting what goes in
boolean[][] marked = new boolean[R][C];
ArrayDeque<int[]> queue = new ArrayDeque<>();
queue.add(new int[] {0, 0});
int count = 1;
marked[0][0] = markGoingIn;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
if (!markGoingIn) {
if (marked[cell[0]][cell[1]]) continue; // the bug's cost: in once for every neighbour that saw it first
marked[cell[0]][cell[1]] = true;
}
for (int[] d : DIRS) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !marked[nr][nc]) {
if (markGoingIn) marked[nr][nc] = true;
queue.add(new int[] {nr, nc});
count++;
}
}
}
return count;
}
static void dfs(int u) {
seen[u] = true;
for (int v : graph.get(u)) {
if (!seen[v]) {
parent[v] = u; // the edge the search first reached v by
dfs(v);
}
}
}
static String shown(int v) {
List<Integer> path = new ArrayList<>();
for (; v != -1; v = parent[v]) path.add(0, v);
StringJoiner s = new StringJoiner(" ");
for (int x : path) s.add(String.valueOf(x));
int used = path.size() - 1;
return s + " (" + used + (used == 1 ? " edge)" : " edges)");
}
public static void main(String[] args) {
System.out.println("marked going in: " + pushes(true) + " pushes for " + R * C + " cells");
System.out.println("marked coming out: " + pushes(false) + " pushes for " + R * C + " cells");
int n = 7;
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {4, 6}, {5, 6}};
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]);
}
parent = new int[n];
Arrays.fill(parent, -1);
seen = new boolean[n];
dfs(0);
System.out.println("DFS's path from 0 to 2: " + shown(2));
Arrays.fill(parent, -1);
seen = new boolean[n];
seen[0] = true;
ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.add(0);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph.get(u)) {
if (!seen[v]) {
seen[v] = true;
parent[v] = u;
queue.add(v);
}
}
}
System.out.println("BFS's path from 0 to 2: " + shown(2));
}
}
// marked going in: 900 pushes for 900 cells
// marked coming out: 1741 pushes for 900 cells
// DFS's path from 0 to 2: 0 1 4 6 5 2 (5 edges)
// BFS's path from 0 to 2: 0 2 (1 edge)#include <bits/stdc++.h>
using namespace std;
const int R = 30, C = 30;
const int DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<int>> graph;
vector<int> parent;
vector<bool> seen;
int pushes(bool markGoingIn) { // a BFS over a 30 x 30 grid of land, counting what goes in
vector<vector<bool>> marked(R, vector<bool>(C, false));
queue<pair<int, int>> q;
q.push({0, 0});
int count = 1;
marked[0][0] = markGoingIn;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
if (!markGoingIn) {
if (marked[r][c]) continue; // the bug's cost: in once for every neighbour that saw it first
marked[r][c] = true;
}
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !marked[nr][nc]) {
if (markGoingIn) marked[nr][nc] = true;
q.push({nr, nc});
count++;
}
}
}
return count;
}
void dfs(int u) {
seen[u] = true;
for (int v : graph[u]) {
if (!seen[v]) {
parent[v] = u; // the edge the search first reached v by
dfs(v);
}
}
}
string shown(int v) {
vector<int> path;
for (; v != -1; v = parent[v]) path.insert(path.begin(), v);
string s;
for (size_t i = 0; i < path.size(); i++) s += (i ? " " : "") + to_string(path[i]);
int used = path.size() - 1;
return s + " (" + to_string(used) + (used == 1 ? " edge)" : " edges)");
}
int main() {
cout << "marked going in: " << pushes(true) << " pushes for " << R * C << " cells\n";
cout << "marked coming out: " << pushes(false) << " pushes for " << R * C << " cells\n";
int n = 7;
vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {4, 6}, {5, 6}};
graph.assign(n, {});
for (auto [u, v] : edges) {
graph[u].push_back(v);
graph[v].push_back(u);
}
parent.assign(n, -1);
seen.assign(n, false);
dfs(0);
cout << "DFS's path from 0 to 2: " << shown(2) << "\n";
parent.assign(n, -1);
seen.assign(n, false);
seen[0] = true;
queue<int> q;
q.push(0);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (!seen[v]) {
seen[v] = true;
parent[v] = u;
q.push(v);
}
}
}
cout << "BFS's path from 0 to 2: " << shown(2) << "\n";
}
// marked going in: 900 pushes for 900 cells
// marked coming out: 1741 pushes for 900 cells
// DFS's path from 0 to 2: 0 1 4 6 5 2 (5 edges)
// BFS's path from 0 to 2: 0 2 (1 edge)const R = 30, C = 30;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function pushes(markGoingIn) { // a BFS over a 30 x 30 grid of land, counting what goes in
const marked = Array.from({ length: R }, () => new Array(C).fill(false));
const queue = [[0, 0]];
let count = 1;
marked[0][0] = markGoingIn;
for (let head = 0; head < queue.length; head++) {
const [r, c] = queue[head];
if (!markGoingIn) {
if (marked[r][c]) continue; // the bug's cost: in once for every neighbour that saw it first
marked[r][c] = true;
}
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !marked[nr][nc]) {
if (markGoingIn) marked[nr][nc] = true;
queue.push([nr, nc]);
count++;
}
}
}
return count;
}
console.log(`marked going in: ${pushes(true)} pushes for ${R * C} cells`);
console.log(`marked coming out: ${pushes(false)} pushes for ${R * C} cells`);
const n = 7;
const edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [4, 6], [5, 6]];
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
let parent = new Array(n).fill(-1), seen = new Array(n).fill(false);
function dfs(u) {
seen[u] = true;
for (const v of graph[u]) {
if (!seen[v]) {
parent[v] = u; // the edge the search first reached v by
dfs(v);
}
}
}
function shown(v) {
const path = [];
for (; v !== -1; v = parent[v]) path.unshift(v);
const used = path.length - 1;
return `${path.join(" ")} (${used} ${used === 1 ? "edge" : "edges"})`;
}
dfs(0);
console.log(`DFS's path from 0 to 2: ${shown(2)}`);
parent = new Array(n).fill(-1);
seen = new Array(n).fill(false);
seen[0] = true;
const queue = [0];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
for (const v of graph[u]) {
if (!seen[v]) {
seen[v] = true;
parent[v] = u;
queue.push(v);
}
}
}
console.log(`BFS's path from 0 to 2: ${shown(2)}`);
// marked going in: 900 pushes for 900 cells
// marked coming out: 1741 pushes for 900 cells
// DFS's path from 0 to 2: 0 1 4 6 5 2 (5 edges)
// BFS's path from 0 to 2: 0 2 (1 edge)const R = 30, C = 30;
const DIRS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function pushes(markGoingIn: boolean): number { // a BFS over a 30 x 30 grid of land, counting what goes in
const marked: boolean[][] = Array.from({ length: R }, () => new Array(C).fill(false));
const queue: [number, number][] = [[0, 0]];
let count = 1;
marked[0][0] = markGoingIn;
for (let head = 0; head < queue.length; head++) {
const [r, c] = queue[head];
if (!markGoingIn) {
if (marked[r][c]) continue; // the bug's cost: in once for every neighbour that saw it first
marked[r][c] = true;
}
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !marked[nr][nc]) {
if (markGoingIn) marked[nr][nc] = true;
queue.push([nr, nc]);
count++;
}
}
}
return count;
}
console.log(`marked going in: ${pushes(true)} pushes for ${R * C} cells`);
console.log(`marked coming out: ${pushes(false)} pushes for ${R * C} cells`);
const n = 7;
const edges: [number, number][] = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [4, 6], [5, 6]];
const graph: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
let parent: number[] = new Array(n).fill(-1), seen: boolean[] = new Array(n).fill(false);
function dfs(u: number): void {
seen[u] = true;
for (const v of graph[u]) {
if (!seen[v]) {
parent[v] = u; // the edge the search first reached v by
dfs(v);
}
}
}
function shown(v: number): string {
const path: number[] = [];
for (; v !== -1; v = parent[v]) path.unshift(v);
const used = path.length - 1;
return `${path.join(" ")} (${used} ${used === 1 ? "edge" : "edges"})`;
}
dfs(0);
console.log(`DFS's path from 0 to 2: ${shown(2)}`);
parent = new Array(n).fill(-1);
seen = new Array(n).fill(false);
seen[0] = true;
const queue: number[] = [0];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
for (const v of graph[u]) {
if (!seen[v]) {
seen[v] = true;
parent[v] = u;
queue.push(v);
}
}
}
console.log(`BFS's path from 0 to 2: ${shown(2)}`);
// marked going in: 900 pushes for 900 cells
// marked coming out: 1741 pushes for 900 cells
// DFS's path from 0 to 2: 0 1 4 6 5 2 (5 edges)
// BFS's path from 0 to 2: 0 2 (1 edge)using System;
using System.Collections.Generic;
class Program {
const int R = 30, C = 30;
static readonly int[][] Dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
static List<int>[] graph;
static int[] parent;
static bool[] seen;
static int Pushes(bool markGoingIn) { // a BFS over a 30 x 30 grid of land, counting what goes in
var marked = new bool[R, C];
var queue = new Queue<int[]>();
queue.Enqueue(new[] {0, 0});
int count = 1;
marked[0, 0] = markGoingIn;
while (queue.Count > 0) {
int[] cell = queue.Dequeue();
if (!markGoingIn) {
if (marked[cell[0], cell[1]]) continue; // the bug's cost: in once for every neighbour that saw it first
marked[cell[0], cell[1]] = true;
}
foreach (int[] d in Dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !marked[nr, nc]) {
if (markGoingIn) marked[nr, nc] = true;
queue.Enqueue(new[] {nr, nc});
count++;
}
}
}
return count;
}
static void Dfs(int u) {
seen[u] = true;
foreach (int v in graph[u]) {
if (!seen[v]) {
parent[v] = u; // the edge the search first reached v by
Dfs(v);
}
}
}
static string Shown(int v) {
var path = new List<int>();
for (; v != -1; v = parent[v]) path.Insert(0, v);
int used = path.Count - 1;
return $"{string.Join(" ", path)} ({used} {(used == 1 ? "edge" : "edges")})";
}
static void Main() {
Console.WriteLine($"marked going in: {Pushes(true)} pushes for {R * C} cells");
Console.WriteLine($"marked coming out: {Pushes(false)} pushes for {R * C} cells");
int n = 7;
int[][] edges = { new[] {0, 1}, new[] {0, 2}, new[] {1, 3}, new[] {1, 4}, new[] {2, 5}, new[] {4, 6},
new[] {5, 6} };
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]);
}
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = -1;
seen = new bool[n];
Dfs(0);
Console.WriteLine($"DFS's path from 0 to 2: {Shown(2)}");
for (int i = 0; i < n; i++) parent[i] = -1;
seen = new bool[n];
seen[0] = true;
var queue = new Queue<int>();
queue.Enqueue(0);
while (queue.Count > 0) {
int u = queue.Dequeue();
foreach (int v in graph[u]) {
if (!seen[v]) {
seen[v] = true;
parent[v] = u;
queue.Enqueue(v);
}
}
}
Console.WriteLine($"BFS's path from 0 to 2: {Shown(2)}");
}
}
// marked going in: 900 pushes for 900 cells
// marked coming out: 1741 pushes for 900 cells
// DFS's path from 0 to 2: 0 1 4 6 5 2 (5 edges)
// BFS's path from 0 to 2: 0 2 (1 edge)package main
import (
"fmt"
"strconv"
"strings"
)
const R, C = 30, 30
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var graph [][]int
var parent []int
var seen []bool
func pushes(markGoingIn bool) int { // a BFS over a 30 x 30 grid of land, counting what goes in
marked := make([][]bool, R)
for i := range marked {
marked[i] = make([]bool, C)
}
queue := [][2]int{{0, 0}}
count := 1
marked[0][0] = markGoingIn
for head := 0; head < len(queue); head++ {
cell := queue[head]
if !markGoingIn {
if marked[cell[0]][cell[1]] {
continue // the bug's cost: in once for every neighbour that saw it first
}
marked[cell[0]][cell[1]] = true
}
for _, d := range dirs {
nr, nc := cell[0]+d[0], cell[1]+d[1]
if nr >= 0 && nr < R && nc >= 0 && nc < C && !marked[nr][nc] {
if markGoingIn {
marked[nr][nc] = true
}
queue = append(queue, [2]int{nr, nc})
count++
}
}
}
return count
}
func dfs(u int) {
seen[u] = true
for _, v := range graph[u] {
if !seen[v] {
parent[v] = u // the edge the search first reached v by
dfs(v)
}
}
}
func shown(v int) string {
path := []string{}
for ; v != -1; v = parent[v] {
path = append([]string{strconv.Itoa(v)}, path...)
}
used := len(path) - 1
word := "edges"
if used == 1 {
word = "edge"
}
return fmt.Sprintf("%s (%d %s)", strings.Join(path, " "), used, word)
}
func main() {
fmt.Printf("marked going in: %d pushes for %d cells\n", pushes(true), R*C)
fmt.Printf("marked coming out: %d pushes for %d cells\n", pushes(false), R*C)
n := 7
edges := [][2]int{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {4, 6}, {5, 6}}
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])
}
reset := func() {
parent = make([]int, n)
for i := range parent {
parent[i] = -1
}
seen = make([]bool, n)
}
reset()
dfs(0)
fmt.Println("DFS's path from 0 to 2: " + shown(2))
reset()
seen[0] = true
queue := []int{0}
for head := 0; head < len(queue); head++ {
u := queue[head]
for _, v := range graph[u] {
if !seen[v] {
seen[v] = true
parent[v] = u
queue = append(queue, v)
}
}
}
fmt.Println("BFS's path from 0 to 2: " + shown(2))
}
// marked going in: 900 pushes for 900 cells
// marked coming out: 1741 pushes for 900 cells
// DFS's path from 0 to 2: 0 1 4 6 5 2 (5 edges)
// BFS's path from 0 to 2: 0 2 (1 edge)Marked on the way out, 900 cells took 1,741 pushes: one for each of the grid's 1,740 edges, plus the start, because each edge put a cell on the queue from whichever end came off first. On the photo's million pixels that would be two million entries where a million do. DFS reached 2 at the end of a path through 1, 4, 6 and 5, 5 edges long, while BFS's first arrival came straight from 0, along 1 edge.
Check yourself
Quiz
1 / 6Multiple choice
A graph has the edges [0, 3], [0, 1], [1, 2], [3, 4], [2, 5] and [4, 5], each vertex's neighbours listed in the order their edges come. In what order does BFS from 0 visit them?
Multiple choice
You need the fewest moves from one cell of a maze to another. Which search do you use?
Multiple choice
A graph has 9 vertices, 0 to 8, and the edges [0, 1], [2, 3], [3, 4] and [5, 6]. How many connected components does it have?
Multiple choice
Why should BFS mark a vertex when it goes into the queue, not when it comes out?
Multiple choice
In Number of Enclaves, you count the land cells that can't walk off the grid. Where should the search start?
Multiple choice
A grid has three islands: three cells in a column, three cells in a row, and an L of three cells. Counting a shape that's turned or flipped as the same shape, how many shapes are there?
Practice
The problems in this group, each mapped to the idea it trains:
- Flood Fill: one search from one cell, the new colour as the mark.
- Depth-First Search: the newest vertex first, by recursion or a stack.
- Breadth-First Search: the oldest vertex first, in layers.
- Number of Islands: one search per island, over a grid.
- Number of Provinces: one search per group, from a matrix.
- Number of Connected Components in an Undirected Graph: one search per group, from edges.
- Connected Components in Grid: groups of cells and their sizes.
- Surrounded Regions: start from the border, flip what it never reaches.
- Number of Enclaves: start from the border, count what's left.
- Pacific Atlantic Water Flow: two searches uphill, one from each ocean.
- Number of Distinct Islands II: a key for each shape, turned and flipped.