import Mathlib /-! # Flood Fill You are given an image represented by an m x n grid of integers image, where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. Your task is to perform a flood fill on the image starting from the pixel image[sr][sc]. To perform a flood fill: Begin with the starting pixel and change its color to color. Perform the same process for each pixel that is directly adjacent (pixels that share a side with the original pixel, either horizontally or vertically) and shares the same color as the starting pixel. Keep repeating this process by checking neighboring pixels of the updated pixels and modifying their color if it matches the original color of the starting pixel. The process stops when there are no more adjacent pixels of the original color to update. Return the modified image after performing the flood fill. ## Constraints - m == image.length - n == image[i].length - 1 <= m, n <= 50 - 0 <= image[i][j], color < 2^16 - 0 <= sr < m - 0 <= sc < n ## Provided examples - `image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]], sr = 1, sc = 1, color = 2` → `[[2, 2, 2], [2, 2, 0], [2, 0, 1]]` - `image = [[0, 0, 0], [0, 0, 0]], sr = 0, sc = 0, color = 0` → `[[0, 0, 0], [0, 0, 0]]` - `image = [[1, 1, 1], [1, 1, 1], [1, 1, 1]], sr = 0, sc = 0, color = 3` → `[[3, 3, 3], [3, 3, 3], [3, 3, 3]]` ## Synthesized negative examples - invalid input: `image = [[0], [0, 0]], sr = 0, sc = 0, color = 0` ([structural] a predicate that admits n == image[i].length. rows of unequal width; a predicate forgetting to check every row accepts it) - invalid input: `image = [[0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0]], sr = 0, sc = 0, color = 1` ([structural] a predicate that admits 1 <= m, n <= 50. fifty-one rows, one past the m ceiling) - invalid input: `image = [[65536]], sr = 0, sc = 0, color = 1` ([structural] a predicate that admits 0 <= image[i][j], color < 2^16. pixel value one past the 16-bit maximum) - `image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]], sr = 1, sc = 1, color = 2` → `[[1, 1, 1], [1, 1, 0], [1, 0, 1]]` is wrong ([structural] no clause requires any pixel to change. original image accepted if modification is not required) - `image = [[0, 0, 0], [0, 0, 0]], sr = 0, sc = 0, color = 0` → `[[0, 0, 0], [0, 0, 0], [0, 0, 0]]` is wrong ([structural] output dimensions are not required to match the input. adds an extra row while all original pixels stay zero) - `image = [[1, 1, 1], [1, 1, 1], [1, 1, 1]], sr = 0, sc = 0, color = 3` → `[[3, 3], [3, 3], [3, 3]]` is wrong ([structural] output rows are not required to have the input's column count. Fills all pixels correctly but drops one column.) -/ namespace PFloodFill abbrev Input := (List (List Nat)) × (Nat) × (Nat) × (Nat) abbrev Output := List (List Nat) /-! ### Specification helpers -/ /-- `p` and `q` are in-bounds cells of `image` that share a side and both carry the start cell's value. -/ def sameColorAdjacent (image : List (List Nat)) (sr sc : Nat) (p q : Nat × Nat) : Prop := p.1 < image.length ∧ p.2 < image[p.1]!.length ∧ q.1 < image.length ∧ q.2 < image[q.1]!.length ∧ (image[p.1]!)[p.2]! = (image[sr]!)[sc]! ∧ (image[q.1]!)[q.2]! = (image[sr]!)[sc]! ∧ ((p.1 = q.1 ∧ (p.2 + 1 = q.2 ∨ q.2 + 1 = p.2)) ∨ (p.2 = q.2 ∧ (p.1 + 1 = q.1 ∨ q.1 + 1 = p.1))) /-- `(r, c)` is joined to `(sr, sc)` by a finite path of side-adjacent cells all carrying the start's original value. -/ def FloodReachable (image : List (List Nat)) (sr sc r c : Nat) : Prop := Relation.ReflTransGen (sameColorAdjacent image sr sc) (sr, sc) (r, c) /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty rectangular grid, at most 50 by 50, of 16-bit pixels, with a 16-bit fill color and an in-bounds start. -/ def isValidInput (input : Input) : Bool := let image := input.1 let sr := input.2.1 let sc := input.2.2.1 let color := input.2.2.2 let n := ((image.head?).getD []).length 1 ≤ image.length && image.length ≤ 50 && 1 ≤ n && n ≤ 50 && image.all (fun row => row.length == n) && image.all (fun row => row.all (fun v => v < 2^16)) && color < 2^16 && sr < image.length && sc < n /-! ### Ideal specification (P_spec) -/ /-- `result` has the shape of `image`, equals `color` at every cell reachable from `(sr, sc)`, and equals `image` at every other cell. -/ def floodFill_spec (input : Input) (result : Output) : Prop := let image := input.1 let sr := input.2.1 let sc := input.2.2.1 let color := input.2.2.2 (result.length = image.length ∧ ∀ r : Nat, r < image.length → (result[r]!).length = (image[r]!).length) ∧ (∀ r : Nat, r < image.length → ∀ c : Nat, c < (image[r]!).length → FloodReachable image sr sc r c → (result[r]!)[c]! = color) ∧ (∀ r : Nat, r < image.length → ∀ c : Nat, c < (image[r]!).length → ¬ FloodReachable image sr sc r c → (result[r]!)[c]! = (image[r]!)[c]!) /-! ### Decidable specification (P_check) -/ /-- The in-bounds cell coordinates of `image`, listed row by row. -/ def gridCells (image : List (List Nat)) : List (Nat × Nat) := (List.range image.length).flatMap fun r => (List.range (image[r]!).length).map fun c => (r, c) /-- Boolean form of `sameColorAdjacent`: both cells in bounds, sharing a side, both carrying the start cell's value. -/ def sameColorStep (image : List (List Nat)) (sr sc : Nat) (p q : Nat × Nat) : Bool := p.1 < image.length && p.2 < image[p.1]!.length && q.1 < image.length && q.2 < image[q.1]!.length && (image[p.1]!)[p.2]! == (image[sr]!)[sc]! && (image[q.1]!)[q.2]! == (image[sr]!)[sc]! && ((p.1 == q.1 && (p.2 + 1 == q.2 || q.2 + 1 == p.2)) || (p.2 == q.2 && (p.1 + 1 == q.1 || q.1 + 1 == p.1))) /-- The grid cells one same-color step away from some cell of `reached`. -/ def stepCells (image : List (List Nat)) (sr sc : Nat) (reached : List (Nat × Nat)) : List (Nat × Nat) := (gridCells image).filter fun q => reached.any fun p => sameColorStep image sr sc p q /-- `reached` closed under `k` rounds of same-color one-step expansion. -/ def closeWithin (image : List (List Nat)) (sr sc : Nat) : Nat → List (Nat × Nat) → List (Nat × Nat) | 0, reached => reached | k + 1, reached => closeWithin image sr sc k ((reached ++ stepCells image sr sc reached).eraseDups) /-- `true` iff `(r, c)` is joined to `(sr, sc)` by a same-color side-adjacent path of in-bounds cells. -/ def floodReached (image : List (List Nat)) (sr sc r c : Nat) : Bool := let cells := gridCells image (closeWithin image sr sc cells.length [(sr, sc)]).contains (r, c) /-- Executable checker for `floodFill_spec`, deciding reachability inside the finite grid. -/ def floodFill_check (input : Input) (result : Output) : Bool := let image := input.1 let sr := input.2.1 let sc := input.2.2.1 let color := input.2.2.2 (result.length == image.length && (List.range image.length).all fun r => (result[r]!).length == (image[r]!).length) && ((List.range image.length).all fun r => (List.range (image[r]!).length).all fun c => !(floodReached image sr sc r c) || (result[r]!)[c]! == color) && (List.range image.length).all fun r => (List.range (image[r]!).length).all fun c => floodReached image sr sc r c || (result[r]!)[c]! == (image[r]!)[c]! /-- A cell is listed by `gridCells` exactly when it is in bounds. -/ theorem mem_gridCells (image : List (List Nat)) (q : Nat × Nat) : q ∈ gridCells image ↔ q.1 < image.length ∧ q.2 < (image[q.1]!).length := by unfold gridCells simp only [List.mem_flatMap, List.mem_range, List.mem_map] constructor · rintro ⟨r, hr, c, hc, rfl⟩ exact ⟨hr, hc⟩ · rintro ⟨h1, h2⟩ exact ⟨q.1, h1, q.2, h2, rfl⟩ /-- The Boolean step agrees with the specification's adjacency relation. -/ theorem sameColorStep_iff (image : List (List Nat)) (sr sc : Nat) (p q : Nat × Nat) : sameColorStep image sr sc p q = true ↔ sameColorAdjacent image sr sc p q := by unfold sameColorStep sameColorAdjacent simp only [Bool.and_eq_true, Bool.or_eq_true, decide_eq_true_eq, beq_iff_eq, and_assoc] /-- Membership in one expansion round. -/ theorem mem_expand (image : List (List Nat)) (sr sc : Nat) (S : List (Nat × Nat)) (q : Nat × Nat) : q ∈ (S ++ stepCells image sr sc S).eraseDups ↔ q ∈ S ∨ (q ∈ gridCells image ∧ ∃ p ∈ S, sameColorStep image sr sc p q = true) := by simp only [stepCells, List.mem_eraseDups, List.mem_append, List.mem_filter, List.any_eq_true] theorem closeWithin_zero (image : List (List Nat)) (sr sc : Nat) (S : List (Nat × Nat)) : closeWithin image sr sc 0 S = S := rfl theorem closeWithin_succ (image : List (List Nat)) (sr sc : Nat) (k : Nat) (S : List (Nat × Nat)) : closeWithin image sr sc (k + 1) S = closeWithin image sr sc k ((S ++ stepCells image sr sc S).eraseDups) := rfl /-- The last round can be peeled off the outside instead of the inside. -/ theorem closeWithin_succ' (image : List (List Nat)) (sr sc : Nat) : ∀ (k : Nat) (S : List (Nat × Nat)), closeWithin image sr sc (k + 1) S = ((closeWithin image sr sc k S) ++ stepCells image sr sc (closeWithin image sr sc k S)).eraseDups := by intro k induction k with | zero => intro S; rfl | succ k ih => intro S rw [closeWithin_succ image sr sc (k + 1) S, ih ((S ++ stepCells image sr sc S).eraseDups), closeWithin_succ image sr sc k S] theorem mem_closeWithin_self (image : List (List Nat)) (sr sc : Nat) : ∀ (k : Nat) (S : List (Nat × Nat)), ∀ x ∈ S, x ∈ closeWithin image sr sc k S := by intro k induction k with | zero => intro S x hx; rw [closeWithin_zero]; exact hx | succ k ih => intro S x hx rw [closeWithin_succ] exact ih _ x ((mem_expand image sr sc S x).mpr (Or.inl hx)) /-- Every listed cell is a seed or an in-bounds grid cell. -/ theorem closeWithin_grid (image : List (List Nat)) (sr sc : Nat) : ∀ (k : Nat) (S : List (Nat × Nat)), ∀ x ∈ closeWithin image sr sc k S, x ∈ S ∨ x ∈ gridCells image := by intro k induction k with | zero => intro S x hx; rw [closeWithin_zero] at hx; exact Or.inl hx | succ k ih => intro S x hx rw [closeWithin_succ] at hx rcases ih _ x hx with h | h · rcases (mem_expand image sr sc S x).mp h with h' | ⟨h', _⟩ · exact Or.inl h' · exact Or.inr h' · exact Or.inr h /-- Soundness: everything the rounds list is reachable from the start. -/ theorem closeWithin_sound (image : List (List Nat)) (sr sc : Nat) : ∀ (k : Nat) (S : List (Nat × Nat)), (∀ x ∈ S, Relation.ReflTransGen (sameColorAdjacent image sr sc) (sr, sc) x) → ∀ x ∈ closeWithin image sr sc k S, Relation.ReflTransGen (sameColorAdjacent image sr sc) (sr, sc) x := by intro k induction k with | zero => intro S h x hx; rw [closeWithin_zero] at hx; exact h x hx | succ k ih => intro S h x hx rw [closeWithin_succ] at hx refine ih _ ?_ x hx intro y hy rcases (mem_expand image sr sc S y).mp hy with hy' | ⟨_, p, hp, hs⟩ · exact h y hy' · exact Relation.ReflTransGen.tail (h p hp) ((sameColorStep_iff image sr sc p y).mp hs) /-- `S` is closed under one same-color step into the grid. -/ def Closed (image : List (List Nat)) (sr sc : Nat) (S : List (Nat × Nat)) : Prop := ∀ q ∈ gridCells image, (∃ p ∈ S, sameColorStep image sr sc p q = true) → q ∈ S /-- A closed list containing the start contains everything reachable from it. -/ theorem closed_reach (image : List (List Nat)) (sr sc : Nat) (S : List (Nat × Nat)) (hstart : (sr, sc) ∈ S) (hcl : Closed image sr sc S) : ∀ x, Relation.ReflTransGen (sameColorAdjacent image sr sc) (sr, sc) x → x ∈ S := by intro x hx induction hx with | refl => exact hstart | tail _ hbc ih => have hstep := (sameColorStep_iff image sr sc _ _).mpr hbc unfold sameColorAdjacent at hbc obtain ⟨_, _, h3, h4, _⟩ := hbc refine hcl _ ?_ ⟨_, ih, hstep⟩ rw [mem_gridCells] exact ⟨h3, h4⟩ /-- Closedness persists through a further round. -/ theorem closed_succ (image : List (List Nat)) (sr sc : Nat) (k : Nat) (S : List (Nat × Nat)) (h : Closed image sr sc (closeWithin image sr sc k S)) : Closed image sr sc (closeWithin image sr sc (k + 1) S) := by intro q hq hex rw [closeWithin_succ'] at hex ⊢ rw [mem_expand] left obtain ⟨p, hp, hs⟩ := hex have hpC : p ∈ closeWithin image sr sc k S := by rcases (mem_expand image sr sc _ p).mp hp with h1 | ⟨h1, h2⟩ · exact h1 · exact h p h1 h2 exact h q hq ⟨p, hpC, hs⟩ /-- Each round from the start either is already closed or strictly grows the set. -/ theorem closeWithin_grow (image : List (List Nat)) (sr sc : Nat) : ∀ k : Nat, Closed image sr sc (closeWithin image sr sc k [(sr, sc)]) ∨ (k + 1 ≤ (closeWithin image sr sc k [(sr, sc)]).toFinset.card ∧ (sr, sc) ∈ gridCells image) := by intro k induction k with | zero => by_cases hs : (sr, sc) ∈ gridCells image · right refine ⟨?_, hs⟩ rw [closeWithin_zero] exact Finset.card_pos.mpr ⟨(sr, sc), List.mem_toFinset.mpr (List.mem_singleton.mpr rfl)⟩ · left intro q hq hex obtain ⟨p, hp, hstep⟩ := hex rw [closeWithin_zero, List.mem_singleton] at hp subst hp exfalso apply hs rw [mem_gridCells] have hstep' := (sameColorStep_iff image sr sc _ _).mp hstep unfold sameColorAdjacent at hstep' exact ⟨hstep'.1, hstep'.2.1⟩ | succ k ih => rcases ih with hc | ⟨hcard, hs⟩ · exact Or.inl (closed_succ image sr sc k _ hc) · by_cases hc : Closed image sr sc (closeWithin image sr sc k [(sr, sc)]) · exact Or.inl (closed_succ image sr sc k _ hc) · right refine ⟨?_, hs⟩ unfold Closed at hc push_neg at hc obtain ⟨q, hq, hex, hnot⟩ := hc have hsub : (closeWithin image sr sc k [(sr, sc)]).toFinset ⊆ (closeWithin image sr sc (k + 1) [(sr, sc)]).toFinset := by intro x hx rw [List.mem_toFinset] at hx ⊢ rw [closeWithin_succ', mem_expand] exact Or.inl hx have hss : (closeWithin image sr sc k [(sr, sc)]).toFinset ⊂ (closeWithin image sr sc (k + 1) [(sr, sc)]).toFinset := by rw [Finset.ssubset_iff_of_subset hsub] refine ⟨q, ?_, ?_⟩ · rw [List.mem_toFinset, closeWithin_succ', mem_expand] exact Or.inr ⟨hq, hex⟩ · rw [List.mem_toFinset] exact hnot have := Finset.card_lt_card hss omega /-- After as many rounds as there are grid cells, the list is closed. -/ theorem closeWithin_closed (image : List (List Nat)) (sr sc : Nat) : Closed image sr sc (closeWithin image sr sc (gridCells image).length [(sr, sc)]) := by rcases closeWithin_grow image sr sc (gridCells image).length with h | ⟨hcard, hs⟩ · exact h · exfalso have hsub : (closeWithin image sr sc (gridCells image).length [(sr, sc)]).toFinset ⊆ (gridCells image).toFinset := by intro x hx rw [List.mem_toFinset] at hx ⊢ rcases closeWithin_grid image sr sc _ _ x hx with h1 | h1 · rw [List.mem_singleton] at h1 rw [h1] exact hs · exact h1 have h1 := Finset.card_le_card hsub have h2 := List.toFinset_card_le (gridCells image) omega /-- The reflection lemma: the checker's reachability test decides `FloodReachable`. -/ theorem floodReached_iff (image : List (List Nat)) (sr sc r c : Nat) : floodReached image sr sc r c = true ↔ FloodReachable image sr sc r c := by show (closeWithin image sr sc (gridCells image).length [(sr, sc)]).contains (r, c) = true ↔ Relation.ReflTransGen (sameColorAdjacent image sr sc) (sr, sc) (r, c) rw [List.contains_iff_mem] constructor · intro h refine closeWithin_sound image sr sc _ _ ?_ _ h intro x hx rw [List.mem_singleton] at hx subst hx exact Relation.ReflTransGen.refl · intro h exact closed_reach image sr sc _ (mem_closeWithin_self image sr sc _ _ _ (List.mem_singleton.mpr rfl)) (closeWithin_closed image sr sc) _ h /-- On valid input the checker accepts exactly the specified outputs. -/ theorem floodFill_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : floodFill_check input result ↔ floodFill_spec input result := by unfold floodFill_check floodFill_spec simp only [Bool.and_eq_true, beq_iff_eq, List.all_eq_true, List.mem_range, Bool.or_eq_true, Bool.not_eq_true', Bool.eq_false_iff, floodReached_iff, and_assoc, or_iff_not_imp_left, not_not] /-! ### Implementation helpers -/ /-- The four side-neighbor candidates of `(r, c)`; truncated subtraction is harmless because `sameColorStep` rejects non-adjacent pairs. -/ def neighborCandidates (r c : Nat) : List (Nat × Nat) := [(r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)] /-- The entry at `(r, c)` of a nested boolean array, or `d` when the coordinate is out of bounds. -/ def getCellBool (a : Array (Array Bool)) (r c : Nat) (d : Bool) : Bool := if h : r < a.size then let row := a[r] if h' : c < row.size then row[c] else d else d /-- Sets the `(r, c)` entry of a nested boolean array, with out-of-bounds writes as no-ops. -/ def setCellBool (a : Array (Array Bool)) (r c : Nat) (v : Bool) : Array (Array Bool) := if h : r < a.size then let row := a[r] if h' : c < row.size then a.set r (row.set c v h') h else a else a /-- Sets the `(r, c)` entry of a nested natural array, with out-of-bounds writes as no-ops. -/ def setCellNat (a : Array (Array Nat)) (r c v : Nat) : Array (Array Nat) := if h : r < a.size then let row := a[r] if h' : c < row.size then a.set r (row.set c v h') h else a else a /-- Breadth-first expansion from `(sr, sc)`: each round probes the frontier's neighbors with `sameColorStep`, marking and recoloring every newly reached cell. -/ def bfsFlood (image : List (List Nat)) (sr sc color : Nat) : List (List Nat) := let grid0 : Array (Array Nat) := (image.map (·.toArray)).toArray let seen0 : Array (Array Bool) := (image.map fun row => (row.map fun _ => false).toArray).toArray let seen := setCellBool seen0 sr sc true let grid := setCellNat grid0 sr sc color let total := image.foldl (fun acc row => acc + row.length) 0 let step := fun (st : Array (Array Bool) × Array (Array Nat) × List (Nat × Nat)) (_ : Nat) => let (seen, grid, frontier) := st let (seen', grid', next) := frontier.foldl (fun (acc : Array (Array Bool) × Array (Array Nat) × List (Nat × Nat)) p => let (seen, grid, next) := acc (neighborCandidates p.1 p.2).foldl (fun (acc2 : Array (Array Bool) × Array (Array Nat) × List (Nat × Nat)) q => let (seen, grid, next) := acc2 if sameColorStep image sr sc p q && !getCellBool seen q.1 q.2 true then (setCellBool seen q.1 q.2 true, setCellNat grid q.1 q.2 color, q :: next) else acc2) (seen, grid, next)) (seen, grid, []) (seen', grid', next) let (_, gridF, _) := (List.range total).foldl step (seen, grid, [(sr, sc)]) gridF.toList.map (·.toList) /-! ### Main algorithm (impl) -/ /-- Flood fill by breadth-first search from `(sr, sc)`, recoloring every same-color side-connected pixel. -/ def runFloodFill (input : Input) : Output := let image := input.1 let sr := input.2.1 let sc := input.2.2.1 let color := input.2.2.2 match ((image[sr]?).getD [])[sc]? with | some v => if v == color then image else bfsFlood image sr sc color | none => image /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem runFloodFill_correct (input : Input) (h : isValidInput input) : floodFill_spec input (runFloodFill input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2) #guard isValidInput ([[0, 0, 0], [0, 0, 0]], 0, 0, 0) #guard isValidInput ([[1, 1, 1], [1, 1, 1], [1, 1, 1]], 0, 0, 3) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([[0], [0, 0]], 0, 0, 0)) #guard !(isValidInput ([[0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0]], 0, 0, 1)) #guard !(isValidInput ([[65536]], 0, 0, 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard floodFill_check ([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2) [[2, 2, 2], [2, 2, 0], [2, 0, 1]] #guard floodFill_check ([[0, 0, 0], [0, 0, 0]], 0, 0, 0) [[0, 0, 0], [0, 0, 0]] #guard floodFill_check ([[1, 1, 1], [1, 1, 1], [1, 1, 1]], 0, 0, 3) [[3, 3, 3], [3, 3, 3], [3, 3, 3]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(floodFill_check ([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2) [[1, 1, 1], [1, 1, 0], [1, 0, 1]]) #guard !(floodFill_check ([[0, 0, 0], [0, 0, 0]], 0, 0, 0) [[0, 0, 0], [0, 0, 0], [0, 0, 0]]) #guard !(floodFill_check ([[1, 1, 1], [1, 1, 1], [1, 1, 1]], 0, 0, 3) [[3, 3], [3, 3], [3, 3]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard runFloodFill ([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2) == [[2, 2, 2], [2, 2, 0], [2, 0, 1]] #guard runFloodFill ([[0, 0, 0], [0, 0, 0]], 0, 0, 0) == [[0, 0, 0], [0, 0, 0]] #guard runFloodFill ([[1, 1, 1], [1, 1, 1], [1, 1, 1]], 0, 0, 3) == [[3, 3, 3], [3, 3, 3], [3, 3, 3]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard floodFill_check ([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2) (runFloodFill ([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2)) #guard floodFill_check ([[0, 0, 0], [0, 0, 0]], 0, 0, 0) (runFloodFill ([[0, 0, 0], [0, 0, 0]], 0, 0, 0)) #guard floodFill_check ([[1, 1, 1], [1, 1, 1], [1, 1, 1]], 0, 0, 3) (runFloodFill ([[1, 1, 1], [1, 1, 1], [1, 1, 1]], 0, 0, 3)) end PFloodFill