10.27

(a) Example with no safe route
For a 3 × 3 grid (X = 3, Y = 3) let

bad =
 [[no, yes, no ],
  [no, yes, no ],
  [no, yes, no ]]

The middle column is a solid wall of “yes”, so every path from the upper-left (0,0) to the lower-right (2,2) is blocked.

(b) Any path in O(XY)
Dynamic programming: sweep once, recording whether a cell is reachable from its north or west neighbour.

reachable[0][0] = (bad[0][0] = no)
for i = 0 .. X-1:
  for j = 0 .. Y-1:
    if bad[i][j] = yes: reachable = false
    else if (i,j) ≠ (0,0):
      reachable[i][j] = reachable[i-1][j] OR reachable[i][j-1]

Store the direction that first set reachable[i][j]; after the sweep, trace predecessors from (X-1,Y-1) back to (0,0) in O(X+Y) time.

(c) Shortest safe path in O(XY)
All edges have equal weight, so a breadth-first search gives the minimum number of blocks.

queue = [(0,0)], dist = ∞, pred = ⌀
while queue not empty:
  (i,j) = pop_front(queue)
  for (u,v) in {(i+1,j),(i-1,j),(i,j+1),(i,j-1)} within grid:
    if bad[u][v]=no and dist[u][v] not set:
      dist[u][v] = dist[i][j] + 1
      pred[u][v] = (i,j)
      push_back(queue,(u,v))

BFS touches every intersection at most once (O(XY)). When (X-1,Y-1) is reached, follow pred pointers back to (0,0) to output the shortest safe route.

Both (b) and (c) use only O(XY) time and O(XY) memory and immediately report “no solution” if the goal cell is never marked reachable.

Back to Chapter 10