{ }codelper

学习 › JavaScript

进阶 · 18

二维列表（网格）

由行和列组成的网格：读取、行和与列和，只在范围内查看相邻格子。

二维列表就是装着列表的列表。
grid[i][j] 表示第 i 行第 j 列的格子。
下面的示例读入网格，求出行和与列和，再输出每个格子相邻格子的和。

const [[r, c], ...grid] = require("fs").readFileSync(0, "utf8").trim().split("\n").map((l) => l.trim().split(/\s+/).map(Number));console.log(grid.map((row) => row.reduce((a, b) => a + b, 0)).join(" "));const colSums = Array.from({ length: c }, (_, j) => grid.reduce((s, row) => s + row[j], 0));console.log(colSums.join(" "));const moves = [[-1, 0], [1, 0], [0, -1], [0, 1]];const near = Array.from({ length: r }, () => new Array(c).fill(0));for (let i = 0; i < r; i++) {  for (let j = 0; j < c; j++) {    for (const [di, dj] of moves) {      const ni = i + di, nj = j + dj;      if (ni >= 0 && ni < r && nj >= 0 && nj < c) near[i][j] += grid[ni][nj];    }  }}for (const row of near) console.log(row.join(" "));
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

要点

  • 要访问所有格子，就在遍历行的循环里再放一个遍历列的循环（嵌套循环）。
  • 行和是把每一行的格子加起来；列和是沿着每一列往下加。
    也可以只遍历一次，同时加到 rowSums[i] 和 colSums[j] 里。
  • 查看相邻格子（上、下、左、右）时，把方向放进列表，比如 di = [-1, 1, 0, 0]、dj = [0, 0, -1, 1]，再循环一遍，代码就短了。
  • 边上的格子，相邻位置会跑到外面。
    读取前一定要检查 0 <= ni < r 且 0 <= nj < c，负数一侧也要查。
  • 每一行都要单独新建。
    同一行放进去好几次的话，改一个格子，所有行都会变。

各语言的写法

Python[[0] * c for _ in range(r)]。
grid[-1] 不是错误，而是最后一行
JavaScriptArray.from({ length: r }, () => new Array(c).fill(0))。
越界的格子是 undefined，在越界的行上读格子会抛出 TypeError
TypeScript和 JavaScript 一样。
类型是 number[][]
Javanew int[r][c] — 全部填 0。
越界报 ArrayIndexOutOfBoundsException
C#有两种：矩形数组 int[r, c]（用 grid[i, j] 读取）和数组的数组 int[r][]。
越界报 IndexOutOfRangeException
C++vector<vector<int>>(r, vector<int>(c))。
[] 不检查范围
C像 int grid[100][100] 这样事先定好大小，只用前面的一部分。
越界读取也不会提示
Craykon每读一行就用 grid.添加(控制台.读数字()) 加进去，用 新列表(c, 0) 创建 c 个 0 的一行。
越界会报“列表只有 0~3 号”的错误

常见错误

漏了范围检查JavaScript · TypeScript · C · C++

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

→ 先输出 NaN，下一行因 TypeError 停止。C 和 C++ 则一声不响地读到下一行或不相干的内存

读取前检查 0 <= ni && ni < r && 0 <= nj && nj < c。
Java、C# 和 Craykon 会因越界错误而停止。

不检查就读第一行的“上邻居”Python

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

→ 3 — grid[-1] 是最后一行，所以不报错，读到了最后一行的值

像 0 <= ni < r 这样，负数一侧也一定要检查。

各语言的差异
Python 的 [[0] * c] * r 让 r 个位置都指向同一行：执行 g = [[0] * 3] * 2; g[0][0] = 5 后得到 [[5, 0, 0], [5, 0, 0]]。
JavaScript 的 new Array(r).fill(new Array(c).fill(0)) 也一样，所以每一行都要单独新建。

练习题

  1. 行和与列和8P0033
  2. 在格子上盖章8P0061
  3. 星号三角形8P0007
  4. 转置并筛选表格1P0083
  5. 两臂不等长的天平8P0345
  6. 螺旋填数8P0128
  7. 两人都有空的天数表8P0234
  8. 温差最大的一天8P0238