{ }codelper

Learn › C

Going further · 18

2D lists (grids)

Grids of rows and columns: reading them, row and column sums, and neighbours inside the bounds.

A 2D list is a list of lists.
grid[i][j] means column j of row i.
The example below reads a grid, finds the row and column sums, and prints the sum of each cell's neighbours.

#include <stdio.h> #define MAX 100 int grid[MAX][MAX]; void print(const int *a, int n) {    for (int i = 0; i < n; i++) printf(i > 0 ? " %d" : "%d", a[i]);    printf("\n");} int main(void) {    int r, c, rowSums[MAX] = {0}, colSums[MAX] = {0};    scanf("%d %d", &r, &c);    for (int i = 0; i < r; i++)        for (int j = 0; j < c; j++) {            scanf("%d", &grid[i][j]);            rowSums[i] += grid[i][j];            colSums[j] += grid[i][j];        }    print(rowSums, r);    print(colSums, c);    const int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};    for (int i = 0; i < r; i++) {        int near[MAX] = {0};        for (int j = 0; j < c; j++)            for (int k = 0; k < 4; k++) {                int ni = i + di[k], nj = j + dj[k];                if (ni >= 0 && ni < r && nj >= 0 && nj < c) near[j] += grid[ni][nj];            }        print(near, c);    }    return 0;}
stdin
3 4
1 2 3 4
5 6 7 8
9 10 11 12
stdout
10 26 42
15 18 21 24
7 10 13 11
16 24 28 23
15 26 29 19

Key points

  • To visit every cell, put a loop over columns inside a loop over rows (a nested loop).
  • Row sums add up the cells of each row; column sums walk down each column.
    You can also add into rowSums[i] and colSums[j] together in one pass.
  • For neighbours (up, down, left, right), keep the directions in lists such as di = [-1, 1, 0, 0] and dj = [0, 0, -1, 1] and loop over them.
    The code gets short.
  • On the edge a neighbour falls outside.
    Always check 0 <= ni < r and 0 <= nj < c before reading, including the negative side.
  • Each row must be created separately.
    If the same row goes in several times, changing one cell changes every row.

How each language writes it

Python[[0] * c for _ in range(r)].
grid[-1] is not an error but the last row
JavaScriptArray.from({ length: r }, () => new Array(c).fill(0)).
A cell outside is undefined; reading a cell of a row outside throws TypeError
TypeScriptSame as JavaScript.
The type is number[][]
Javanew int[r][c] — filled with zeros.
Out of range: ArrayIndexOutOfBoundsException
C#Two kinds: the rectangular array int[r, c] (read with grid[i, j]) and the jagged array of arrays int[r][].
Out of range: IndexOutOfRangeException
C++vector<vector<int>>(r, vector<int>(c)).
[] does not check the range
CFix the size in advance, like int grid[100][100], and use only the top-left part.
Reading out of range says nothing
CraykonBuild it row by row with grid.Add(Console.ReadNumbers()), and make a row of c zeros with NewList(c, 0).
Out of range stops with an error saying the list only has items 0 to 3

Common mistakes

Skipping the range checkJavaScript · TypeScript · C · C++

const grid = [[1, 2], [3, 4]];
console.log(1 + grid[0][2]);
console.log(grid[2][0]);

→ Prints NaN, then the next line stops with a TypeError. C and C++ silently read the next row or unrelated memory

Check 0 <= ni && ni < r && 0 <= nj && nj < c before reading.
Java, C# and Craykon stop with an index error.

Reading the top row's upper neighbour without a checkPython

grid = [[1, 2], [3, 4]]
i, j = 0, 0
print(grid[i - 1][j])

→ 3 — grid[-1] is the last row, so it quietly reads from the bottom row

Check the negative side too: 0 <= ni < r.

How languages differ
Python [[0] * c] * r makes r references to one and the same row: after g = [[0] * 3] * 2; g[0][0] = 5 you get [[5, 0, 0], [5, 0, 0]].
JavaScript new Array(r).fill(new Array(c).fill(0)) does the same, so always create each row separately.

Practice

  1. Row and column sums8P0033
  2. Stamping a grid8P0061
  3. Star triangle8P0007
  4. Flip and filter a grid1P0083
  5. A balance with unequal arms8P0345
  6. Spiral fill8P0128
  7. Table of shared free days8P0234
  8. The day with the widest swing8P0238