Introduction

Matrix 是二维数组。涉及 matrix 的题通常和 dynamic programming 或 graph 遍历相关。

Matrix 可用来表示 graph：每个 cell 是 node，通常有 4 个邻居（边界与角落除外）。本页聚焦“不把 matrix 当 graph”的题型；如果要把 matrix 当 graph，请看 graph section。

Corner cases

在 traversal 或 DP 题里，几乎总需要创建一个同尺寸的空矩阵，用来存 visited state 或 DP table。要熟悉你所用语言的写法。

Python 一行写法：

# Assumes that the matrix is non-empty
zero_matrix = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]

Python 拷贝 matrix：

copied_matrix = [row[:] for row in matrix]

Transpose 是把行变成列、列变成行。

很多 grid-based game（如 Tic-Tac-Toe、Sudoku、Crossword、Connect 4、Battleship）都可用 matrix 建模，经常要检查横向/纵向的胜利条件。一个技巧是：先写横向验证逻辑，然后对 matrix 转置，复用横向逻辑来验证原本的纵向。

Python 转置：

transposed_matrix = zip(*matrix)

该 topic 必练题。

在掌握基础后推荐练习。