Flood fill

Questions 1 to 5 of 7

1. 1. This version of the fill is meant to count the cells it fills, but on a 3 by 3 grid of dots it crashes. What is the bug? ``cpp int fillLate(vector<string>& grid, int r, int c) { if (r < 0 || r >= (int)grid.size()) return 0; if (c < 0 || c >= (int)grid[r].size()) return 0; if (grid[r][c] != '.') return 0; int count = 1; count += fillLate(grid, r - 1, c); count += fillLate(grid, r + 1, c); count += fillLate(grid, r, c - 1); count += fillLate(grid, r, c + 1); grid[r][c] = '*'; return count; } ``

   The bounds check is wrong. It should use >= on the column, so the fill stops one cell early.The function returns 1 before the recursive calls are made, so the fill stops after one cell.Each neighbour calls back to this cell while it still reads ., so the calls never end and the stack runs out. Moving the mark above the first recursive call fixes it.The count is wrong, but the fill is correct, because the centre cell is never visited.
2. 2. The author removed one line from this fill. What goes wrong on a 3 by 4 grid? ``cpp int fill(vector<string>& grid, int r, int c, char open) { if (r < 0 || r >= (int)grid.size()) return 0; if (c < 0 || c >= (int)grid[r].size()) return 0; grid[r][c] = '*'; int count = 1; count += fill(grid, r - 1, c, open); count += fill(grid, r + 1, c, open); count += fill(grid, r, c - 1, open); count += fill(grid, r, c + 1, open); return count; } ``

   The count is one too small, because the first cell is not counted.Nothing stops the recursion. A marked cell still calls its four neighbours, which call back, so the calls never end and the program crashes.The bounds check on the rows is missing, so the fill reads past the last row once and prints a wrong count.Only the top-left cell is filled, because the line grid[r][c] = '*'; ends the function early.
3. 3. Put the four steps of one call to the fill function in the order the call runs them.

   Use the arrows to put the steps in order.

   1. 1.Change the cell to '*' and set the count to 1↑↓
   2. 2.Call the same function on the four neighbours and add their counts↑↓
   3. 3.Stop if the cell is not the open character, such as a wall or a filled cell↑↓
   4. 4.Stop if the row or column is outside the grid↑↓
4. 4. Put these steps of the island counter in order.

   Use the arrows to put the steps in order.

   1. 1.At an unmarked land cell, call fill on it so the whole island is marked↑↓
   2. 2.Add one to the island count for that island↑↓
   3. 3.Carry on scanning, so every cell is checked and no island is counted twice↑↓
   4. 4.Scan every cell of the grid, row by row, starting from the top-left↑↓
5. 5. What does this program print? ``cpp #include <iostream> #include <string> #include <vector> using namespace std; int fill(vector<string>& grid, int r, int c, char open) { if (r < 0 || r >= (int)grid.size()) return 0; if (c < 0 || c >= (int)grid[r].size()) return 0; if (grid[r][c] != open) return 0; grid[r][c] = '*'; int count = 1; count += fill(grid, r - 1, c, open); count += fill(grid, r + 1, c, open); count += fill(grid, r, c - 1, open); count += fill(grid, r, c + 1, open); return count; } int main() { vector<string> grid = {"..#", ".#.", "..."}; int n = fill(grid, 0, 0, '.'); cout << n << "\n"; for (const string& row : grid) cout << row << "\n"; } ``

   6 **# *#* ***7 ..# .#. ...7 **# *#* ***9 *** *#* ***