Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 63 ยท Ad Hoc and Implementation

Grid and Matrix Tricks

Master grid problems: direction arrays, border padding, flood fill, rotating and transposing matrices, and 2D prefix sums for constant-time rectangle sums.

Grids appear in a huge share of contest problems: mazes, boards, maps, images, tables of numbers. They look different from each other, but a small set of tricks handles nearly all of them. With these tricks, the code that moves around a grid stays short, and short code has fewer bugs.

This lesson covers five tools: direction arrays for stepping to neighbours, border padding to avoid bounds checks, flood fill to find connected regions, rotations and transposes to reshape a matrix, and 2D prefix sums to answer rectangle-sum queries instantly. Earlier lessons showed grids in implementation problems; here we make them fast and tidy. Breadth-first search on grids is explained from the graph point of view in graph problems: modeling and traversal.

Direction arrays

Instead of writing four copies of "go up, down, left, right", store the offsets once and loop:

Python
DIRS4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
DIRS8 = DIRS4 + [(-1, -1), (-1, 1), (1, -1), (1, 1)]

Now "visit all neighbours of (r, c)" is a two-line loop, and switching from 4-connected to 8-connected movement is changing one name. Chess knights use eight different offsets, (ยฑ1, ยฑ2) and (ยฑ2, ยฑ1), which fits the same pattern.

flowchart LR
  A["Cell (r, c)"] --> B["For each (dr, dc)<br/>in DIRS"]
  B --> C["nr = r + dr<br/>nc = c + dc"]
  C --> D{"Inside the grid<br/>and allowed?"}
  D -- "yes" --> E["Use neighbour (nr, nc)"]
  D -- "no" --> B

The neighbour loop: apply each offset, test the bounds, use the cell if it is valid.

Padding the border

The bounds check 0 <= nr < n and 0 <= nc < m is repeated everywhere, and forgetting it causes either a crash or, worse in Python, a silent bug: a negative index like grid[-1] does not raise an error, it reads the last row.

A cleaner approach is to pad the grid with a frame of sentinel cells that behave like walls. Then every real cell has all its neighbours inside the array, and the sentinel blocks movement naturally.

Python Counting islands with a padded grid and flood fill

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two points make this code robust:

  1. No recursion. A flood fill on a 1000 by 1000 grid could recurse a million levels deep and crash Python. An explicit stack (or a queue) has no such limit.
  2. Mark cells when you push them, not when you pop them. Otherwise the same cell may be pushed many times by different neighbours, and the work blows up.

The same loop with a queue and a distance array gives the shortest path in an unweighted maze; that is the next step in the graphs chapter.

Flood fill for regions

Flood fill answers questions such as "how many regions", "what is the size of the largest region", "is this cell connected to the border" and "which cells are enclosed". A common trick for the last two is to flood from the outside: pad the grid, start filling from the frame, and everything left unfilled is enclosed.

When the regions are defined by equal values instead of #, compare the neighbour's value to the start value. For counting connected components, union-find is an alternative that also handles cells being added over time.

Rotations, transposes and flips

A matrix is a list of rows. Python's zip(*m) regroups the columns, which is exactly a transpose. Combined with reversing, it gives all the rotations in one line each:

Operation Code
Transpose [list(r) for r in zip(*m)]
Rotate 90ยฐ clockwise [list(r) for r in zip(*m[::-1])]
Rotate 90ยฐ counter-clockwise [list(r) for r in zip(*m)][::-1]
Flip horizontally [r[::-1] for r in m]
Flip vertically m[::-1]
Python Rotate, transpose and compare orientations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the rotation of a 2 by 3 matrix is a 3 by 2 matrix. Square-only formulas for in-place rotation break on rectangles, which is why building a new list is usually the safer choice. To test whether two shapes are the same "up to rotation and reflection", list the eight orientations and check membership, as the last lines do.

2D prefix sums

A prefix sum stores running totals so that any range sum becomes a subtraction. In two dimensions, let P[i][j] be the sum of the rectangle from the top-left corner down to row i-1 and column j-1. Then the sum of any sub-rectangle needs only four lookups, using inclusion and exclusion:

sum(r1..r2, c1..c2) = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

The extra row and column of zeros at the top and left are the same padding idea as before: they remove special cases at the edges.

flowchart LR
  A["Full block<br/>P[r2+1][c2+1]"] --> B["minus the rows above<br/>P[r1][c2+1]"]
  B --> C["minus the columns left<br/>P[r2+1][c1]"]
  C --> D["add back the corner<br/>P[r1][c1]"]

Inclusion-exclusion: the corner was subtracted twice, so it is added back once.

Python Rectangle sums in O(1) with a 2D prefix table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Building the table costs O(nm) once, and each query then costs O(1). With a grid of 1000 by 1000 and 10^5 queries, the brute force would need up to 10^11 operations, while the prefix table needs about 10^6 plus 10^5. The one-dimensional version and the difference array for range updates are in Prefix Sums and Difference Arrays; see also prefix sums in DSA.

Reading grids safely

  • Read rows as strings: rows = [input() for _ in range(n)]. Index with rows[r][c].
  • Convert to a list of lists only if you need to modify cells; strings are immutable.
  • Find special cells while reading: for r, row in enumerate(rows): c = row.find("S").
  • Decide once whether you use (row, column) or (x, y); mixing them is the classic transposition bug.
  • For the layout of fast input in Python, see Python for contests.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main benefit of padding a grid with a frame of wall cells?

    With a frame of blocked cells, neighbour lookups never leave the array. It also avoids the Python pitfall where index -1 silently reads the last element.
  2. 2. Why mark a cell as visited when pushing it onto the stack instead of when popping it?

    If cells are only marked on pop, several neighbours can push the same cell before it is processed, which wastes time and can cause duplicate counting.
  3. 3. Which expression rotates a matrix m by 90 degrees clockwise?

    Reversing the rows and then transposing with zip(*...) rotates clockwise. The first option is just a transpose; the others are flips.
  4. 4. With P as a 2D prefix table (with a leading row and column of zeros), which formula gives the sum of rows r1..r2 and columns c1..c2?

    Subtract the rows above and the columns to the left, then add back the corner that was subtracted twice.

Summary

  • Direction arrays turn neighbour logic into a short loop; one list switches between 4, 8 or knight moves.
  • Pad the grid with sentinel walls to avoid bounds checks and the negative-index trap.
  • Use an explicit stack or queue for flood fill, and mark cells when you push them.
  • zip(*m) transposes; combined with reversing it gives every rotation and flip.
  • A 2D prefix table answers rectangle sums in O(1) after O(nm) preprocessing.
  • Always test grid code on 1 by 1, one row and one column inputs.

Next: Binary Search on Answer for Contests