Grid search and state BFS in Python

Questions 1 to 5 of 8

1. 1. What does this program print? ``python def fill(g, r, c): if r < 0 or r >= len(g) or c < 0 or c >= len(g[r]) or g[r][c] != "A": return 0 g[r][c] = "X" return 1 + fill(g, r + 1, c) + fill(g, r - 1, c) + fill(g, r, c + 1) + fill(g, r, c - 1) g = [list("AAB"), list("ABA"), list("AAA")] n = fill(g, 0, 0) print(n, "".join(g[1])) ``

   6 XBA7 XBA7 XBX3 XBX
2. 2. What does this program print? ``python keys = 0 keys |= 1 << (ord("b") - ord("a")) keys |= 1 << (ord("d") - ord("a")) can_open_b = (keys & (1 << (ord("B") - ord("A")))) != 0 can_open_c = (keys & (1 << (ord("C") - ord("A")))) != 0 print(keys, can_open_b, can_open_c) ``

   2 True False10 True False10 False True10 True True
3. 3. A search keeps one seen mark per cell. On the grid #a## and @.Ab, the correct answer is 5, but the search returns -1. Why?

   Door A is a wall, so no route can ever reach it.The middle cell was marked seen while no key was held. When the search returns to it with key a, it is skipped, so door A is never tried.The key a is inside a wall, so it can never be picked up.The search stops after the first key it picks up.
4. 4. The state search returns as soon as it removes a state that holds every key. Why is that first answer the smallest number of steps?

   It tries the cheapest key first, so the first full key set it finds is always the smallest.It always explores the whole grid before it checks for the goal.Doors add extra steps, so the goal is always reached by the shortest route.It handles states in order of step count, so when a full key set is removed, no route with fewer steps is still waiting in the queue.
5. 5. Which statements about the grid fill and island counting in the earlier grid lesson are true? Pick all that apply.

   Pick every answer that is true.

   The count_islands function changes the grid that the caller passed in.Painting a cell when it is added to the queue means each cell enters the queue only once.The recursive fill can raise RecursionError on a very large region of one colour.The four neighbour moves in DIRECTIONS include the diagonal moves, so diagonal touches join islands.The bounds check must come before the grid is read at that row and column.