12.4 Grid paths and constraints

A grid is a special kind of graph. Each usable cell is a vertex, and each permitted move between neighbouring cells is an edge. The rows and columns tell us where the vertices are, so we can generate their neighbours without drawing every edge. Once we have this graph, the BFS and DFS methods from Module 12.3 work just as they do on a network of named circles: BFS finds the fewest equal-cost moves, while DFS can test whether a route exists.

The grid adds rules that affect which edges exist. A wall blocks a cell or move. A locked door may be passable only after collecting a key. If future moves depend on a key, remaining energy, or direction, the search must remember that information along with the cell. This is intermediate graph search built on coordinates from Module 10.1. MIT OpenCourseWare's graph-search lecture supplies the search method; the grid supplies its neighbours.

A basic idea: a movement rule creates the edges

For a four-neighbour grid, a cell $(r,c)$ can move to $(r-1,c)$, $(r+1,c)$, $(r,c-1)$, or $(r,c+1)$ when that destination is inside the grid and open. These are exactly its graph neighbours. Eight-neighbour movement also allows diagonals. State which convention the question uses: a diagonal changes both reachability and shortest-route length. Also say whether a diagonal may pass between blocked cells if the problem has that rule.

A quick tour of movement constraints

For an unweighted grid, BFS finds the fewest moves because every legal move costs one edge. Store the start, a queue, a visited set, and the parent of each discovered state. Check boundaries and walls before adding a neighbour. DFS can answer whether a route exists but its first route may not be shortest.

The key question is what makes two visits equivalent? If you can carry a key, the state is $(r,c,\text{hasKey})$, not just $(r,c)$. Reaching a cell with the key can enable moves that were impossible on an earlier visit without it. Likewise, with a limited number of wall breaks, store the number used or remaining. Marking only the cell as visited can discard a valid route.

If moves have unequal costs, ordinary BFS no longer minimizes total cost. A question about the fewest turns may need direction in the state as well: $(r,c,\text{direction})$. Choose a state containing exactly the facts needed to decide future legal moves and cost.

Application 1: shortest route around a wall

In a $3$ by $3$ grid, the centre cell $(1,1)$ is blocked. You may move up, down, left, or right. What is the minimum number of moves from $(0,0)$ to $(2,2)$?

1. Find a lower bound. The row must increase twice and the column twice, so at least $4$ moves are needed.
2. Give a valid route. $(0,0)\to(0,1)\to(0,2)\to(1,2)\to(2,2)$ uses $4$ moves and avoids the centre.
3. Conclude. The lower bound is met, so $4$ is the minimum. BFS would find one of the edge routes in its fourth layer.

Application 2: a key before a door

The pictured grid has top row $S,\cdot,D,G$, then a row with one open cell below $S$ and walls elsewhere, then $K$ below that open cell and walls elsewhere. The door $D$ opens only after collecting the key $K$. What is the shortest four-neighbour route?

1. Go to the key. From $S=(0,0)$, move to $(1,0)$ and $K=(2,0)$: two moves.
2. Return and finish. Move back through $(1,0)$ and $S$, then right through $(0,1)$, $D=(0,2)$, and $G=(0,3)$: five more moves, seven total.
3. Explain the state. The second visit to $S$ has $\text{hasKey}=1$, unlike the first visit. BFS must treat them as distinct states to use the door.

The walls make the door the only route to the goal.