Grids

A grid is a table of cells, such as a maze, a game board or a map, usually given as rows of characters. Most grid problems need the neighbours of a cell, visited with one loop over a short list of moves and a check that each neighbour is inside the grid. To find the shortest route through a maze, see BFS.

Explanation

A minefield has 4 rows and 6 columns. Each cell is a mine, written *, or empty, written ., and the input gives each row as a line of 6 characters, a string. A cell is named by its row, then its column, both counted from 0. The mine in the second row is cell (1, 3). Row 0 is at the top, so going up makes the row number smaller.

Fig. 1. Cell (1, 3) is in row 1 and column 3.

Minesweeper shows, for every empty cell, how many mines touch it; start with the cells that share a side. Cell (1, 2) has four side neighbours: up (0, 2), down (2, 2), left (1, 1) and right (1, 3). Each is the cell plus a small change: −1 or +1 to the row, or to the column. Four ifs count the mines among them, and for (1, 2) they give 2:

int mines = 0;
if (g[r - 1][c] == '*') mines++;   // up
if (g[r + 1][c] == '*') mines++;   // down
if (g[r][c - 1] == '*') mines++;   // left
if (g[r][c + 1] == '*') mines++;   // right

Run the same four lines for the corner cell (0, 0). The first line reads row −1, and the third reads column −1. Neither exists. The right count is 1, but C++ gives no error: it reads whatever lies in memory there, so the count can be wrong or the program can crash.

Fig. 2. The red dashed cells outside the grid don't exist, so the corner cell (0, 0) has only 2 side neighbours.

So each if needs its own inside check: the row is from 0 to R - 1 and the column from 0 to C - 1, for $R$ rows and $C$ columns. The line for up becomes if (r - 1 >= 0 && g[r - 1][c] == '*') mines++;, and the other three grow the same way. Minesweeper also counts the corner neighbours, the cells that touch at a corner, so there are 8 neighbours: the 3×3 block around the cell, without the cell itself.

Fig. 3. The 4 side neighbours of (1, 2) are blue and the 4 corner neighbours orange. Three of the 8 are mines, (0, 1), (1, 3) and (2, 2), so the number of (1, 2) is 3.

That makes 8 lines, each with its own check. They differ only in the row change and the column change, and each line is one more chance to get a sign or a bound wrong.

Instead, write the changes once, in two short arrays called direction arrays: one holds the row change of each direction, the other its column change. For the side neighbours they are −1, +1, 0, 0 and 0, 0, −1, +1, so direction 0 is up, 1 down, 2 left and 3 right.

One loop goes over the directions. For each one it computes the neighbour, skips it if it is outside the grid, and only then uses it. With the 8 changes of Fig. 3 in the arrays, the same loop visits the corner neighbours too. At the corner (0, 0), 5 of the 8 changes land outside and are skipped. One of the 3 cells inside is a mine, so the Minesweeper number of (0, 0) is 1.

Fig. 4. The loop at (0, 0) skips the 5 changes that land outside the grid.

A problem needs this when it says "adjacent", "shares a side" or "shares a side or a corner", or when it draws a map of characters.

In C++

The input usually gives R and C, then R lines. When each row is one word of characters, store the grid as vector<string> g(R) and read each row with cin >> g[r]; the cell (r, c) is the character g[r][c], and g[r][c] == '*' checks for a mine. The number of rows is g.size(), of columns g[0].size(). When the cells are numbers separated by spaces, use a vector<vector<int>> a(R, vector<int>(C)) and read it with two nested loops, cin >> a[r][c].

The direction arrays are dr for the row change and dc for the column change. The loop over k, the neighbour loop, is the same in every grid problem.

// read the grid
int R, C;
cin >> R >> C;
vector<string> g(R);
for (int r = 0; r < R; r++) cin >> g[r];

int dr[] = {-1, 1, 0, 0};   // up, down, left, right
int dc[] = {0, 0, -1, 1};

// the side neighbours of cell (r, c)
for (int k = 0; k < 4; k++) {                                  // each direction
    int nr = r + dr[k], nc = c + dc[k];                        // the neighbour
    if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;     // outside the grid
    // use it: (nr, nc) is inside the grid
}

Instead of the inside check, some programs store the grid inside a frame: one extra row and column of . on each side. The 4×6 minefield becomes 6×8, its own cells are in rows 1 to R and columns 1 to C, and the loops over the cells run from 1. Every side and corner neighbour is then in memory. This works only when every change is −1, 0 or +1, and only when the frame's character stops the loop: a walk that keeps going while cells are . runs through a . frame and past the end of the string.

Counting the mines around every cell

The Minesweeper program runs the neighbour loop for every cell, with the 8-entry arrays. It prints * for a mine and, for every other cell, the number of mines among its 8 neighbours.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    // read the grid
    int R, C;
    cin >> R >> C;
    vector<string> g(R);
    for (int r = 0; r < R; r++) cin >> g[r];

    int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};   // the 3×3 block around the cell, without the cell
    int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};

    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (g[r][c] == '*') {
                cout << '*';
                continue;
            }
            int mines = 0;
            for (int k = 0; k < 8; k++) {                                // each direction
                int nr = r + dr[k], nc = c + dc[k];                      // the neighbour
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;   // outside the grid
                if (g[nr][nc] == '*') mines++;                           // use it
            }
            cout << mines;
        }
        cout << '\n';
    }
}

Each of the R \cdot C cells looks at 8 neighbours, so the program takes O(8 \cdot R \cdot C) = O(R \cdot C) time and no memory beyond the grid. The arrays can hold other moves too: with a knight's 8 jumps in them, the same loop visits the cells a knight attacks.

Walking in one direction

The same arrays walk in a straight line: keep stepping by dr[k] and dc[k] while the next cell is inside the grid and empty, to find how far a rook sees or how long a ship is. With the side arrays, k = 3 walks right. From (3, 0) the walk counts 3 empty cells, not counting the start, and stops before the mine at (3, 4).

int steps = 0;
int nr = r + dr[k], nc = c + dc[k];   // the neighbour
while (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] != '*') {
    steps++;
    nr += dr[k];
    nc += dc[k];
}

&& checks its parts from left to right and stops at the first false one. With the inside check first, g[nr][nc] is read only for a cell inside the grid.

Fig. 5. The walk keeps adding (0, +1) until the next cell is a mine or outside the grid.

When a walk turns, as in a spiral, order the arrays clockwise, dr = {0, 1, 0, -1} and dc = {1, 0, -1, 0} for right, down, left and up. Then k = (k + 1) % 4 turns right.

A cell as one number

Some problems number the cells left to right, top to bottom, and some algorithms, such as a DSU, want each cell as one number. Cell (r, c) becomes id = r * C + c, and back r = id / C, c = id % C. On the minefield, cell (2, 2) is 2 · 6 + 2 = 14, and 14 / 6 = 2, 14 % 6 = 2. If the problem numbers cells from 1, subtract 1 first.

Fig. 6. Each row starts C = 6 numbers after the one above it. 14 / 6 gives the row, 14 % 6 the column.

int id = r * C + c;            // cell (r, c) as one number
int r2 = id / C, c2 = id % C;  // and back

Common mistakes

• Reading a neighbour before checking it, as in if (g[nr][nc] == '*' && nr >= 0 && ...). At (0, 0), direction 0 reads g[-1][0] before the check can reject row −1. Put the check first or on its own continue line.

• Swapping rows and columns, as in nr >= C or g[c][r]. On a square sample it works; on the 4×6 minefield, cell (0, 5) read as g[5][0] is a row that doesn't exist. Keep r with R and the first index, and if the input gives the width first or (x, y), rename once while reading.

• Storing coordinates given from 1 as they are. Every mine moves one cell down and right, and one in the last row lands in row R, outside. Write g[r - 1][c - 1] = '*' when reading.

• Counting the cell as its own neighbour, with a double loop over changes from −1 to 1 that doesn't skip (0, 0). A program that also gave each mine a number would give the mine at (0, 1) a 1 instead of 0, because it counts itself. Skip (0, 0) or use the 8-entry arrays.

• Reading rows that contain spaces with cin >> g[r], which stops at a space. The row X S X is read as the three strings X, S and X, so the rows after it shift by two. Read each row with getline, after discarding the end of the first line:

  cin >> R >> C;
  string rest;
  getline(cin, rest);   // the end of the line with R and C
  for (int r = 0; r < R; r++) getline(cin, g[r]);

Similar techniques

• Flood fill visits a whole region of touching cells, such as a lake, with the neighbour loop inside a search. Connected components run it from every unvisited cell to count the regions, such as islands.

• BFS finds the fewest moves between two cells of a maze. Multi-source BFS finds the distance to the nearest of many cells, such as fires or exits.

• An adjacency list stores a graph's edges. A grid is a graph whose edges are not stored: the direction arrays compute them.

• Grid paths count paths that move only right and down, with dynamic programming rather than neighbour checks.

• 2D prefix sums give the sum over any rectangle of a grid.

Practice