Grids are graphs: neighbours, bounds and costs

Graphs Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
rows, cols = 3, 4
r, c = 0, 3
steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
nbrs = [(r + dr, c + dc) for dr, dc in steps
        if 0 <= r + dr < rows and 0 <= c + dc < cols]
print(nbrs)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [(1, 3), (0, 2)]

Right: a corner cell has only two neighbours inside the grid.

Corner cells have two neighbours, edge cells three and inner cells four, which is why edges are at most 4·R·C.

Why not the others?
  • B [(1, 3), (-1, 3), (0, 4), (0, 2)]. The bounds check removes cells outside the grid.
  • C [(1, 3)]. Moving left to (0, 2) stays inside the grid.

30-second answer

Each cell is a node and its neighbours are the cells up, down, left and right (sometimes diagonals too). You never build an adjacency list; you compute neighbours from coordinates and check bounds. With R rows and C columns there are R·C nodes and at most 4·R·C edges, so BFS and DFS are O(R·C).

Practise saying it · 30 s. No recording, just a timer

Explain how to treat a grid as a graph.

Say your answer out loud, then check which of these points you covered:

  • Cells are nodes
  • Compute neighbours, check bounds
  • O(R·C)

Deep dive

A direction list like ((1, 0), (-1, 0), (0, 1), (0, -1)) keeps the neighbour code short and bug-free.

Encode a cell as r * C + c if you need a single integer key.

Ask whether you may mark visits in the grid itself or need a separate seen set.

Common mistakes

  • Mixing up rows and columns in bounds checks.
  • Forgetting diagonals when the question includes them, or adding them when it does not.

Senior take & follow-ups

Write the bounds check once in a helper or in one condition; it is where most grid bugs live.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you handle a grid with walls and keys?

    Show hint

    Make the state (row, col, keys held) and BFS over states.

  2. What about very large or infinite grids?

    Show hint

    BFS with a dict of visited cells and a limit, or A* with a distance heuristic.

What each operation costs: Breadth First Search · Depth First Search · Topological Sort · Dijkstra Algorithm

Try it in a free tool

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.