Flood fill

Questions 1 to 5 of 7

1. 1. The fill function below labels a region, but it writes the label after the four neighbour calls. The lists grid and labels are defined at module level. What goes wrong? ``python def fill(row, col, label): if row < 0 or row >= len(grid): return if col < 0 or col >= len(grid[0]): return if grid[row][col] != 1: return if labels[row][col] != 0: return fill(row - 1, col, label) fill(row + 1, col, label) fill(row, col - 1, label) fill(row, col + 1, label) labels[row][col] = label ``

   The bounds checks should use > instead of >=, so the last row is skipped.A neighbour can call back into this cell before it is labelled, so the check on labels still passes and the calls never end.The function should return the label count instead of None.The grid must be copied before the four calls, or the labels overwrite the grid.
2. 2. The grid list is a 2 by 2 list where every value is 1, defined at module level. This function is called as fill_wrong_bound(0, 0). ``python def fill_wrong_bound(row, col): if row < 0 or row > len(grid): return if col < 0 or col >= len(grid[0]): return if grid[row][col] != 1: return grid[row][col] = 2 fill_wrong_bound(row + 1, col) fill_wrong_bound(row, col + 1) `` What does the program do?

   It returns after all four cells are filled, with no error.It stops at once with a RecursionError, because the cells call each other.It raises IndexError: list index out of range, because row 2 passes the row check and the program then reads grid[2].It prints nothing, because the first cell is blocked.
3. 3. Put the steps of one call of fill(row, col, label) in the order they run.

   Use the arrows to put the steps in order.

   1. 1.Write the label into the cell↑↓
   2. 2.Call fill on the cell above, below, left and right↑↓
   3. 3.Return at once if the cell is blocked (its value is not 1) or already has a label↑↓
   4. 4.Return at once if row or col is outside the grid↑↓
4. 4. Put the steps of the labelling program in the order they run.

   Use the arrows to put the steps in order.

   1. 1.Scan every cell with two nested loops↑↓
   2. 2.Call fill on that cell with the value of next_label↑↓
   3. 3.When a cell is open and has no label, add 1 to next_label↑↓
   4. 4.Create labels with the same number of rows and columns as grid↑↓
   5. 5.Print each row of labels, then the number of regions↑↓
5. 5. What is the third line printed by this program? ``python grid = [list("#.."), list("##."), list("..#")] def region_size(row, col): if row < 0 or row >= len(grid): return 0 if col < 0 or col >= len(grid[row]): return 0 if grid[row][col] != ".": return 0 grid[row][col] = "#" return ( 1 + region_size(row - 1, col) + region_size(row + 1, col) + region_size(row, col - 1) + region_size(row, col + 1) ) print(f"first: {region_size(0, 1)}") print(f"second: {region_size(0, 1)}") print(f"third: {region_size(2, 0)}") ``

   third: 1third: 3third: 0third: 2