Algorithms / Grid Coordinate Reasoning
Least You Need to Know: Grid Coordinates, Neighbor Rules, and Unweighted Shortest Paths
Grid problems are geometry disguised as arrays. The reusable ideas are bounds checks, choosing the correct neighborhood model, and remembering that BFS solves unweighted shortest paths while visited-state tracking prevents the scan from bouncing forever.
The least you need to know
- A valid grid cell `(r, c)` must satisfy `0 <= r < rows` and `0 <= c < cols`.
- Four-neighbor movement matches Manhattan-style up/down/left/right steps; eight-neighbor movement is a different graph.
- BFS gives shortest path length in an unweighted grid.
- Visited tracking prevents repeated work and infinite revisits.
- The grid is a graph: cells are nodes and allowed moves are edges.
Key notation
(r, c)
row and column coordinates
|r1-r2| + |c1-c2|
Manhattan distance
BFS layer
all cells at the same unweighted distance
Tiny worked example
- In a maze where each step has equal cost, treat each open cell as a node.
- Add edges to valid neighboring cells.
- BFS expands layer by layer, so the first time you reach the target you have found a shortest path.
Common mistakes
- A diagonal move changes the graph model and can invalidate a shortest-path argument built for four neighbors.
- Bounds checks should happen before reading grid contents at a candidate coordinate.
- DFS can find a path, but it does not guarantee the shortest unweighted path the way BFS does.
How to recognize this kind of problem
- The prompt describes movement on rows and columns or flood fill over cells.
- Each move has the same cost, making BFS a strong default for shortest-path questions.
- The problem mentions islands, mazes, components, or reachable cells in a matrix.