二维数组、坐标与边界处理

02 / 学习目标与先修自测

学完本课你能做什么，以及开始前需要会什么

读题时定下 m 行 n 列，访问前先判边界，填充题先算内容再处理排版。

先修自测：下面 5 题请先自己写答案，再展开对照。答不出的按括号里的位置补看再回来。本课假定你会上一课的逐字符扫描与列表操作。

03 / 概念与术语

行列、宽高、0/1 基、方向数组、边界函数

网格题的错误大半来自约定不统一。把每个名字的含义和代码写法先定下来，本课和模块 3 都按同一套用。

关于「长宽」：P2503 的题面写「输入 m, n 表示长宽」，随后是 m 行、每行 n 个数——所以 m 是行数、n 是列数，与「m 行 n 列」一致。遇到只写「长宽」不写「行列」的题，按输入格式里「接下来 m 行」这句话定行数，再用非方阵样例（如 2 行 3 列）跑一遍确认没接反。

04 / 边界与遍历

越界检查：固定成一个函数

把「先判边界」写成一个函数，所有访问都经过它——这一个习惯能消除网格题里大半的运行错误（RE）和不报错的答案错误（WA）。

grid = [[0,0,0],[0,0,0],[1,0,0]]   # 只有 (2,0) 有车
只判上界（r < m and c < n）、不判下界时：
  (0,0) 的「上」邻居 (−1,0) 通过判定 → grid[-1][0] 取到最后一行 → 读到 1 → (0,0) 被误判为需要监控
C++ 里 grid[-1][0] 是运行错误；Python 里它合法地取到最后一行，错误从运行错误变成难查的答案错误
结论：下界 0 <= r 和 0 <= c 必须写，而且判定要发生在取值之前

# 练习模板：请补全下面标注为「步骤」的部分，其余可直接保留
import sys

def main() -> None:
    data = sys.stdin.read().split()
    # 步骤 1：在这里读出 m 行 n 列（先确认题目给出的是「行列」还是「宽高」）
    m = n = 0
    grid = [[0] * n for _ in range(m)]
    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    def in_bounds(r: int, c: int) -> bool:
        return 0 <= r < m and 0 <= c < n
    # 步骤 2：在这里写遍历/填充逻辑——访问邻居前必须先调用 in_bounds
    # 步骤 3：按题目要求的格式打印矩阵（行内分隔符、行末不多空格）

main()

原矩阵      转置后      逐行反转后（= 顺时针 90°）
1 2 3       1 4 7       7 4 1
4 5 6   →   2 5 8   →   8 5 2
7 8 9       3 6 9       9 6 3
映射: (0,0)→(0,2)  (2,1)→(1,0)  一般式 (i, j) → (j, n − 1 − i)

grid_ok = [[0] * 3 for _ in range(2)]
grid_bad = [[0] * 3] * 2

grid_ok[0][0] = 1   # 只改第一行
grid_bad[0][0] = 1  # 两行一起变

assert grid_ok == [[1, 0, 0], [0, 0, 0]]
assert grid_bad == [[1, 0, 0], [1, 0, 0]]

05 / 完整手算例：P2503

逐格判定「自身或四邻有车」

P2503「统计监控」：m 行 n 列的停车场，0 空位、1 有车；一个车位的监控器需要打开，当且仅当它自己或上下左右四个相邻车位里有车。输出需要打开的监控器数量。题面样例在题目页查看；下面用自拟的 3×3 样例逐格推演。

行 0: (0,0) 四邻 (1,0)(0,1) 都是 0 → 不开 | (0,1) 下邻 (1,1)=1 → 开 | (0,2) 四邻 (1,2)(0,1) 都是 0 → 不开
行 1: (1,0) 右邻 (1,1)=1 → 开 | (1,1) 自己有车 → 开 | (1,2) 左邻 (1,1)=1 → 开
行 2: (2,0) 不开 | (2,1) 上邻 (1,1)=1 → 开 | (2,2) 不开
输出 5（车位自己 + 上下左右四个）

06 / 完整手算例：P2529

螺旋填充：每一段与四个边界变量的值

P2529「螺旋数字矩阵」：给数字个数 n 和行数 m，从左上角的 1 开始顺时针向内依次填 1…n；每行个数相同、列数尽可能少（cols = ⌈n/m⌉）、优先填外圈、数字不够的格子用单个 * 填充。下面用 n=9、m=4 完整推演。

上行 (0,2,0,3): 1 2 3 4        → top=1
右列 (1,2,0,3): (1,3)=5 (2,3)=6 → right=2
下行 (1,2,0,2): (2,2)=7 (2,1)=8 (2,0)=9 → bottom=1
左列 (1,1,0,2): (1,0)=10      → left=1
上行 (1,1,1,2): (1,1)=11；num=12 > 11 停止 → (1,2) 保持 *
输出: 1 2 3 4 / 10 11 * 5 / 9 8 7 6

停止条件以 num > n（数字用完）为主：列数按 n/m 向上取整，格子数不少于 n，所以数字总会在格子用完之前或恰好同时用完，num > n 单独就能让本程序正常结束。上边界超过下边界、左边界超过右边界这两条区间判断是防御性的，保证四条边各自收缩后不会去访问已经不存在的行列；对本程序的合法输入，去掉它们输出不变。真正会出错的是边界不收缩：n=9、m=3 时 cols=3、正好填满，最后一圈只剩中心一格 (1,1)，由「上行」这一段填入 9 后停止；若漏掉 top += 1，第二段「右列」会从第 0 行重新开始，把 (0,2) 的 3 覆盖成 4，第 08 节错误表给出了完整输出。

07 / 从步骤到程序

两道必做题的完整参考程序，每一步落在哪几行

先自己写完并提交一次，再展开对照；对照时用第 05、06 节的手算例逐格核对。

import sys

data = sys.stdin.read().split()
m, n = int(data[0]), int(data[1])                 # m 行 n 列（题面写「长宽」；用样例确认哪个是行数）
grid = [[int(data[2 + i * n + j]) for j in range(n)] for i in range(m)]

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]          # 上、下、左、右

def in_bounds(r, c):
    return 0 <= r < m and 0 <= c < n

count = 0
for r in range(m):
    for c in range(n):
        need = grid[r][c] == 1                       # 自己有车
        if not need:
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if in_bounds(nr, nc) and grid[nr][nc] == 1:   # 先判边界，再取值
                    need = True
                    break
        if need:
            count += 1
print(count)

import sys

n, m = map(int, sys.stdin.read().split())          # n 个数字，m 行
cols = (n + m - 1) // m                            # 列数尽可能少：向上取整 n/m
grid = [["*"] * cols for _ in range(m)]            # 先全填 *，数字不够的格子保持 *

top, bottom, left, right = 0, m - 1, 0, cols - 1   # 四个边界
num = 1
while num <= n and top <= bottom and left <= right:
    for c in range(left, right + 1):               # 上行：从左到右
        if num > n: break
        grid[top][c] = str(num); num += 1
    top += 1
    for r in range(top, bottom + 1):               # 右列：从上到下
        if num > n: break
        grid[r][right] = str(num); num += 1
    right -= 1
    for c in range(right, left - 1, -1):           # 下行：从右到左
        if num > n or top > bottom: break
        grid[bottom][c] = str(num); num += 1
    bottom -= 1
    for r in range(bottom, top - 1, -1):           # 左列：从下到上
        if num > n or left > right: break
        grid[r][left] = str(num); num += 1
    left += 1

for row in grid:
    print(" ".join(row))

08 / 边界、反例与复杂度

错误做法在具体输入上各输出什么

下面每一行都是一个具体的错误程序，给出输入、错误输出与正确输出；把参考程序改成对应写法就能复现。

09 / 渐进练习与参考答案

跟做 → 改一个条件 → 独立实现 → 迁移

每题先在纸上或文件里做完，再展开答案。

练习 1（跟做）：3 行 4 列的网格（m=3，n=4），写出 (0,0)、(0,3)、(1,1)、(2,2)、(1,3) 各有几个合法四邻，并列出 (1,3) 的合法邻居坐标。

练习 2（改一个条件）：P2503 输入 2 3 / 1 0 1 / 0 0 0 改成 2 3 / 1 0 0 / 0 0 1，输出什么？

练习 3（改一个条件）：P2529 输入 5 3，先算列数，再按四段填充写出输出。

练习 4（独立实现）：不看参考程序，写出 in_bounds 与「返回合法四邻列表」的 neighbors(r, c)，让下面的断言通过（m=n=3）。

m, n = 3, 3
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def in_bounds(r, c):
    return 0 <= r < m and 0 <= c < n

def neighbors(r, c):
    return [(r + dr, c + dc) for dr, dc in DIRS if in_bounds(r + dr, c + dc)]

assert len(neighbors(1, 1)) == 4          # 中心
assert len(neighbors(0, 1)) == 3          # 边
assert len(neighbors(0, 0)) == 2          # 角
assert neighbors(0, 0) == [(1, 0), (0, 1)]
assert not in_bounds(-1, 0) and not in_bounds(0, 3)   # 负下标与右越界都判为出界

练习 5（迁移）：用第 04 节补充学习里的映射 (i, j) → (j, n − 1 − i)，写出 3×3 矩阵顺时针旋转 90° 后原来 (0,2)、(1,0)、(2,2) 三个位置各落到哪里，并用旋转后的矩阵 [[7,4,1],[8,5,2],[9,6,3]] 验证。

10 / 读题要求、基础加练与复习自评

两道题的要求对照，以及完成本课之后怎么复习

提交前把下表过一遍；题目页的题面与样例是最终依据。

题解入口：需要对照解法时，先展开本课第 07 节的两份完整参考程序；两道题的题目页另有思路与 Python / Java / C++ 参考代码，可在题目页查看。基础加练：本页下方「基础加练（选做）」的 4 道题（H100054 搜索二维矩阵 II、H100051 矩阵置零、H100053 旋转图像、H100052 螺旋矩阵）分别练坐标移动、先读后写、旋转映射、四条边界，与第 04、06 节一一对应。

复习与自评：本课算完成 = 两道必做题 P2503、P2529 都通过判题，并勾选全部六条「学习完成检查」；基础加练与复习题不影响完成状态。六条检查是自评，不改变题目的通过（AC）状态。复习时用三个问题自测：① 不看正文，写出方向数组和边界判定式，并说出漏掉下界会发生什么；② 不看表格，重算 n=9、m=4 的螺旋填充每一段的边界变量；③ 说出 P2503 里 m、n 各是行数还是列数、怎样用非方阵样例验证。答不出哪一条，就回到对应的节重读，再做第 09 节对应的练习。

基础加练（选做）

同一主题的 5 道基础题

这组题目采用标准输入输出（ACM 模式）：程序从标准输入读取数据、把结果写到标准输出。它们难度低于必做题，适合在必做题之前热身，或在未通过时回来巩固；不计入本课完成标准。每道题给出练习重点、完成标准与提示；已在本站通过的题目会直接显示为已通过。

• ·H100054未开始

  搜索二维矩阵 II

  基础练习 1：坐标移动 · 预计 18 分钟

  练习重点：

  从右上角出发，每次排除一行或一列

  完成标准：

  能解释当前值过大为什么左移，过小为什么下移

  提示

  右上角左边的数更小、下边的数更大。和目标值（target）比较后，选择能排除整列或整行的方向。

  打开题目看动画讲解
• ·H100051未开始

  矩阵置零

  基础练习 2：先读后写 · 预计 20 分钟

  练习重点：

  两遍扫描，先保存原始 0 的行列，再修改矩阵

  完成标准：

  能解释为什么扫描时立刻置零会让新写出的 0 继续扩散

  提示

  第一遍把原始 0 所在的行号和列号分别放进集合；第二遍再判断每个位置是否需要改成 0。

  打开题目看动画讲解
• ·H100053未开始

  旋转图像

  重点练习 · 预计 30 分钟

  练习重点：

  坐标映射、顺时针方向，以及不会覆盖旧值的写入顺序

  完成标准：

  能说出 (i, j) 到 (j, n - 1 - i)，并比较新矩阵和原地做法

  提示

  先在纸上给 3×3 矩阵编号。可以先用新矩阵确认坐标方向；通过后，再尝试沿主对角线转置，然后反转每一行。

  打开题目看动画讲解
• ·H100052未开始

  螺旋矩阵

  进阶练习：四条边界 · 预计 25 分钟

  练习重点：

  维护上、下、左、右四个边界变量（top、bottom、left、right），按右、下、左、上收缩

  完成标准：

  单行、单列和中心格都只会加入答案一次

  提示

  走完上边界和右边界后，先判断上下、左右是否交错，再决定是否继续走下边界和左边界。

  打开题目看动画讲解
• ·H100056未开始

  搜索二维矩阵

  进阶练习：矩阵中的二分查找 · 预计 20 分钟

  练习重点：

  把二维矩阵看成一条升序数组，再把中点下标 mid 映射回行列

  完成标准：

  能写出行号 row = mid // n 和列号 col = mid % n，并说明题目为何满足整体有序

  提示

  只有每行首元素都大于上一行末元素时，矩阵才能按行拼成完整升序数组。二分得到 mid 后，用整除和取模还原坐标。

  打开题目看动画讲解