Matrix

A 2D grid is a graph you never have to build: each cell is a vertex, and its neighbours are the cells one step away. Every problem in this section is the BFS or DFS you already know, with the neighbour function swapped for a pair of direction offsets and a bounds check.

The theory - the implicit edges, DIRS4 vs DIRS8, the four ways to track visited, flood fill, multi-source and border-seeded seeding, and what to do when a cell has a cost - is all on Grids as Graphs.

Practice

• DFS - connected components (the islands family) and the border-seeded inversion.
• BFS - shortest path and elapsed-time questions, single- and multi-source.