Lesson 14: 迷宫出路判断 CNB
练习任务
本课包含两个递进练习：
练习 1（棋盘初始化与打印）：用全局二维数组 chessboard[ROW][COL] 表示一个 5×5 的棋盘。实现 init_chessboard() 用 my_rand() % 2 随机填充 0 或 1，实现 print_chessboard() 按行列格式打印。0 表示可通行，1 表示障碍物。
期望输出（5×5 矩阵）：
1 1 1 1 0
1 1 0 1 1
0 0 0 0 1
0 1 1 1 1
1 0 0 0 0练习 2（方向检查）：用 struct direction { int dr; int dc; char name[16]; } 定义四个方向（上/下/左/右），实现 int check(int row, int col, dir_t dir) 判断从 (row, col) 沿 dir 方向是否可通行（新位置在棋盘内且值为 0）。对位置 (1, 1) 的期望输出是 down 和 right 两个方向可走。
提示：方向数组是处理网格/棋盘的经典技巧——用一对数组
{dx, dy}或一个结构体{dr, dc}编码上下左右四个方向的偏移量，然后用for循环依次尝试所有方向。边界检查is_valid()是防止数组越界的最后一道防线。
核心知识点
- 二维数组声明与索引 —
chessboard[ROW][COL]，board[i][j]访问第 i 行第 j 列 - 二维数组作为函数参数 —
void print(int board[ROW][COL])传递时需指定列数 - 行优先存储（Row-Major） — C 语言二维数组按行存储，同行元素在内存中连续
- 方向数组 —
dirx[4] = {-1, 1, 0, 0}和diry[4] = {0, 0, -1, 1}编码四个方向 struct direction— 用结构体替代两个独立数组，方向有dr、dc和name字段- 结构体数组 —
dir_t dirs[4]初始化为四个方向配置，遍历时语义更清晰 - 边界检查
is_valid— 访问board[x][y]前必须验证索引在0~ROW-1和0~COL-1内 - 全局数组初始化 —
int board[ROW][COL] = 0批量清零 - 伪随机数 LCG —
seed = seed * 1103515245 + 12345的跨平台确定性 - DFS 深度优先搜索概念 — 从当前位置出发递归探索所有可达点
代码框架
练习 1：棋盘初始化与打印
c
#include <stdio.h>
#define ROW 5
#define COL 5
int chessboard[ROW][COL];
// 平台无关的伪随机数生成器
static unsigned int seed = 42;
int my_rand(void) {
seed = seed * 1103515245 + 12345;
return (seed >> 16) & 0x7fff;
}
void init_chessboard(void)
{
int i, j;
// 双层 for 循环: chessboard[i][j] = my_rand() % 2
}
void print_chessboard(void)
{
int i, j;
// 双层 for 循环: 打印每个元素 + 换行
}
int main(void)
{
init_chessboard();
print_chessboard();
return 0;
}练习 2：方向结构体与检查
c
#include <stdio.h>
#define ROW 5
#define COL 5
int chessboard[ROW][COL];
/* ... 初始化代码同上 ... */
int is_valid(int row, int col)
{
// 检查 row 和 col 是否在棋盘范围内
if (/* row 越界？ */) return 0;
if (/* col 越界？ */) return 0;
return 1;
}
struct direction {
int dr; // 行的偏移量
int dc; // 列的偏移量
char name[16]; // 方向名
};
typedef struct direction dir_t;
dir_t dirs[4] = {
{-1, 0, "up"},
{ 1, 0, "down"},
{ 0, -1, "left"},
{ 0, 1, "right"},
};
int check(int row, int col, dir_t dir)
{
int nr = row + dir.dr;
int nc = col + dir.dc;
// 如果 (nr,nc) 在棋盘内 且 chessboard[nr][nc] == 0 → 返回 1
// 否则返回 0
}
int main(void)
{
int row, col, i, ways = 0;
init_chessboard();
scanf("%d %d", &row, &col);
for (i = 0; i < 4; i++)
{
int ret = check(row, col, dirs[i]);
if (ret > 0)
{
printf("direction %s is ok!\n", dirs[i].name);
ways++;
}
}
printf("value = %d\n", chessboard[row][col]);
printf("ways = %d\n", ways);
return 0;
}填充框架的关键思考：is_valid 中越界判断怎么写（row < 0 还是 row < ROW）？check 中 nr 和 nc 怎么从 dir.dr 和 dir.dc 计算？如果只想检查四个方向中的某一个方向，还需要 for 循环吗？
TIP
先不要往下翻看参考解答。尝试先实现 14a（棋盘初始化打印）以确保二维数组操作熟悉，再攻 14b（方向检查）。用 my_rand() 而不是标准库的 rand()，因为前者保证跨平台输出一致。
深度讲解
1. 二维数组：棋盘的数据承载
1.1 声明与索引
c
#define ROW 5
#define COL 5
int board[ROW][COL]; // 5 行 5 列的整数矩阵
board[0][0] = 0; // 第 0 行第 0 列
board[2][3] = 1; // 第 2 行第 3 列索引规则：
board[row][col]——row从 0 到ROW-1，col从 0 到COL-1- 第一个下标是行，第二个下标是列
- 这与数学矩阵的惯例一致：
A[i][j]表示第i行第j列
1.2 二维数组的内存布局：行优先（Row-Major）
c
#include <stdio.h>
int board[5][5];
int main(void)
{
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
board[i][j] = i * 5 + j;
// 同一行的元素在内存中是连续的
printf("board[0][0] = %d, addr = %p\n", board[0][0], (void*)&board[0][0]);
printf("board[0][1] = %d, addr = %p\n", board[0][1], (void*)&board[0][1]);
printf("board[1][0] = %d, addr = %p\n", board[1][0], (void*)&board[1][0]);
// board[0][4] 紧挨着 board[1][0] —— 行优先：一行接一行排列
return 0;
}内存中的实际排列（行优先，Row-Major）：
[0,0] [0,1] [0,2] [0,3] [0,4] [1,0] [1,1] [1,2] ... [4,4]
├──── 第 0 行 (5 个元素) ────┤├──── 第 1 行 ────────┤
board[i][j] 的内存地址 = base + (i * COL + j) * sizeof(int)一维索引等价公式：board[i][j] 等价于用一维方式访问 board[i * COL + j]。
地址差异验证：以下程序验证同行和跨行的地址跳跃：
c
#include <stdio.h>
int board[3][4];
int main(void)
{
printf("board[0][0] addr = %p\n", (void*)&board[0][0]);
printf("board[0][1] addr = %p (+%td)\n",
(void*)&board[0][1],
(char*)&board[0][1] - (char*)&board[0][0]); // +4 (一个 int)
printf("board[0][3] addr = %p (+%td)\n",
(void*)&board[0][3],
(char*)&board[0][3] - (char*)&board[0][0]); // +12
printf("board[1][0] addr = %p (+%td)\n",
(void*)&board[1][0],
(char*)&board[1][0] - (char*)&board[0][0]); // +16 (一整行的偏移)
printf("sizeof(board[0]) = %zu\n", sizeof(board[0])); // 16 = 4 ints × 4 bytes
printf("sizeof(board) = %zu\n", sizeof(board)); // 48 = 3 × 16
return 0;
}输出验证了关键事实：board[1][0] 紧挨在 board[0][3] 之后——行优先意味着跨行时地址连续跳跃一整行的宽度。
sizeof 的行为：
sizeof(board)= 整个二维数组的大小 (ROW * COL * sizeof(int))sizeof(board[0])= 一行的大小 (COL * sizeof(int))sizeof(board[0][0])= 一个元素的大小 (sizeof(int))
1.3 二维数组作为函数参数
c
// 正确：必须指定列数 COL
void init(int board[ROW][COL]) { ... }
// 也可以省略行数（因为编译器不需要知道），但列数必须写
void init(int board[][COL], int rows) { ... }
// ↑
// 列数必须明确，编译器需要它来计算 board[i][j] 的偏移量
// 错误：只写二维括号不写维数
void init(int board[][]) { ... } // 编译错误为什么列数必须显式指定：编译器在计算 board[i][j] 的地址时，需要知道一行有多长（即 sizeof(int) * COL），才能从第 i 行跳到第 j 列。
1.4 全局二维数组的初始化
c
// 方式 1：全零初始化（回顾 Lesson 04 BSS 段）
int board[ROW][COL] = {{0}}; // 全部元素设为 0
// 方式 2：逐行指定（C99 指定初始化）
int board[3][3] = {
{1, 0, 1},
{0, 1, 0},
{1, 0, 1}
};
// 方式 3：扁平化初始化（按行优先顺序）
int board[3][3] = {1, 0, 1, 0, 1, 0, 1, 0, 1}; // 同上2. 方向数组：网格探索的经典技巧
2.1 朴素写法 vs 方向数组
朴素写法（4 个方向各自硬编码）：
c
// 上
if (onboard(x-1, y) && board[x-1][y] == 0) ways++;
// 下
if (onboard(x+1, y) && board[x+1][y] == 0) ways++;
// 左
if (onboard(x, y-1) && board[x][y-1] == 0) ways++;
// 右
if (onboard(x, y+1) && board[x][y+1] == 0) ways++;方向数组写法（统一循环）：
c
int dirx[4] = {-1, 1, 0, 0}; // 四个方向的行偏移
int diry[4] = { 0, 0, -1, 1}; // 四个方向的列偏移
for (int i = 0; i < 4; i++)
{
int nx = x + dirx[i];
int ny = y + diry[i];
if (onboard(nx, ny) && board[nx][ny] == 0)
{
ways++;
printf("direction %d is ok\n", i);
}
}方向数组的优势：
- 新增方向只需改数组——从 4 个变为 8 个只需改数组定义，循环体不变
- 可复用——同一个方向数组用于多个位置
- 可读性——方向和代码逻辑分离
2.2 从整数数组到结构体数组的进化
c
// 版本 1：两个独立整数数组（语义分离）
int dirx[4] = {-1, 1, 0, 0};
int diry[4] = {0, 0, -1, 1};
// 版本 2：用结构体把方向打包（语义整合）
struct direction {
int dr; // 行偏移
int dc; // 列偏移
char name[16]; // 方向名
};
dir_t dirs[4] = {
{-1, 0, "up"},
{ 1, 0, "down"},
{ 0, -1, "left"},
{ 0, 1, "right"},
};版本 2 明显更优：方向的所有属性（偏移量、名称）都在一个对象中，新增方向只需在数组中加一行。遍历时 printf("direction %s is ok!\n", dirs[i].name) 直接输出人类可读的方向名。
2.3 扩展方向：8 方向（加上对角线）
c
dir_t dirs[8] = {
{-1, 0, "up"},
{ 1, 0, "down"},
{ 0, -1, "left"},
{ 0, 1, "right"},
{-1, -1, "up-left"},
{-1, 1, "up-right"},
{ 1, -1, "down-left"},
{ 1, 1, "down-right"},
};
// 把循环上界从 4 改为 8，其余代码完全不变！这正是方向数组的灵活之处——算法框架不变，改变数组内容即可适配不同需求。
2.4 方向数组设计模式总结
方向数组是网格类算法中最重要的抽象之一。以下是一个通用的网格遍历模板，适用于后续所有棋盘/迷宫/图像类算法：
c
// 通用网格遍历模板
#define ROWS 10
#define COLS 10;
int board[ROWS][COLS];
int visited[ROWS][COLS] = {0};
// 定义方向（可扩展至 8 个或更复杂的移动规则）
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
int num_dirs = 4;
void traverse(int start_r, int start_c)
{
// 对每个方向尝试一步
for (int d = 0; d < num_dirs; d++)
{
int nr = start_r + dr[d];
int nc = start_c + dc[d];
// 模板检查：边界 + 障碍 + 已访问
if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS)
continue; // 出界 → 下一个方向
if (board[nr][nc] == 1)
continue; // 障碍 → 下一个方向
if (visited[nr][nc])
continue; // 已访问 → 下一个方向
// 到达这里：该方向可以走
visited[nr][nc] = 1;
// 在这里做你想做的事情（计数/打印/递归...）
}
}这个模板是后续 DFS/BFS/回溯算法的共同基础——把 // 在这里做你想做的事情 换成递归调用就是 DFS，换成队列入队就是 BFS。
棋盘坐标系统图解：
棋盘坐标系统 (chessboard[row][col]):
col →
row ┌───┬───┬───┬───┬───┐
↓ │0,0│0,1│0,2│0,3│0,4│ ← 第 0 行
├───┼───┼───┼───┼───┤
│1,0│1,1│1,2│1,3│1,4│ ← 第 1 行
├───┼───┼───┼───┼───┤
│2,0│2,1│2,2│2,3│2,4│
├───┼───┼───┼───┼───┤
│3,0│3,1│3,2│3,3│3,4│
├───┼───┼───┼───┼───┤
│4,0│4,1│4,2│4,3│4,4│ ← 第 4 行
└───┴───┴───┴───┴───┘
方向偏移的含义:
dr=-1, dc=0 → 上移一行（row 减 1）
dr=+1, dc=0 → 下移一行（row 加 1）
dr=0, dc=-1 → 左移一列（col 减 1）
dr=0, dc=+1 → 右移一列（col 加 1）3. 边界检查：is_valid 的生命防线
3.1 为什么需要边界检查
c
int board[5][5];
// 如果不检查，以下访问会导致数组越界
board[-1][3] = 1; // row = -1，非法！
board[0][-1] = 1; // col = -1，非法！
board[5][0] = 1; // row = 5，超出 0~4
board[0][5] = 1; // col = 5，超出 0~4C 语言不会自动检查数组越界——越界写入会悄无声息地破坏其他变量的值或导致段错误。
3.2 is_valid 的标准写法
c
int is_valid(int row, int col)
{
if (row < 0 || row >= ROW) // 行越界
return 0;
if (col < 0 || col >= COL) // 列越界
return 0;
return 1; // 在范围内
}短路求值的作用：row < 0 || row >= ROW 中，如果 row < 0 已经为真，row >= ROW 不会被求值——这是 C 语言逻辑运算符的基本特性。
3.3 越界访问的后果示意
假设栈上内存布局:
┌─────────┬─────────┬─────────┬─────────┬─────┐
│ board │ board │ i (循环│ j (循环│ ... │
│ [0][0] │ [0][1] │ 变量) │ 变量) │ │
└─────────┴─────────┴─────────┴─────────┴─────┘
board[-1][0] = 999; → 可能覆盖了 j 的值！循环行为异常
board[5][0] = 999; → 可能覆盖了 i 的值！循环行为异常CAUTION
数组越界是 C 语言中最常见的 bug 之一。一定要在任何 board[x][y] 访问前检查 is_valid(x, y)。格式化打印时虽然不会崩溃，但方向检查如果漏了边界判断，可能在棋盘边缘方向直接访问非法内存。
4. 棋盘遍历的模式
4.1 行优先遍历
c
// 按行遍历：先走第 0 行的所有列，再走第 1 行...
for (int i = 0; i < ROW; i++) // 外层：行
for (int j = 0; j < COL; j++) // 内层：列
printf("%d ", board[i][j]);
printf("\n");
}这是最常见的遍历模式——与二维数组的 Row-Major 内存布局一致，缓存友好（Cache-friendly）。
遍历顺序:
row=0 → [0,0] [0,1] [0,2] [0,3] [0,4]
row=1 → [1,0] [1,1] [1,2] [1,3] [1,4]
...4.2 列优先遍历
c
// 按列遍历：先走第 0 列的所有行，再走第 1 列...
for (int j = 0; j < COL; j++) // 外层：列
for (int i = 0; i < ROW; i++) // 内层：行
process(board[i][j]);
}
}这种遍历模式与 Row-Major 内存布局不匹配，可能导致更多 cache miss。除非问题本身要求按列处理（如图像处理中的列操作），否则优先用行优先遍历。
4.3 边界哨兵（Sentinel）技巧
c
// 在棋盘周围加一圈「围墙」，避免边界检查
#define BOARD_SIZE 7 // 5 + 2 边
int board[BOARD_SIZE][BOARD_SIZE];
// 初始化时，四周设为 1（墙），内部正常填充
// 这样任何「走出棋盘」的尝试都会撞到墙，无需 is_valid 检查这是 DFS/BFS 中的一种优化技巧——通过扩展棋盘并在四周加障碍物，省去了 is_valid 检查。但对于入门来说，显式的边界检查更直观。
4.4 其他遍历模式：蛇形与螺旋
c
// 蛇形（Zig-Zag）遍历：偶数行从左到右，奇数行从右到左
for (int i = 0; i < ROW; i++)
{
if (i % 2 == 0)
{
// 偶数行：从左到右
for (int j = 0; j < COL; j++)
printf("%d ", board[i][j]);
}
else
{
// 奇数行：从右到左
for (int j = COL - 1; j >= 0; j--)
printf("%d ", board[i][j]);
}
printf("\n");
}蛇形遍历路径示意:
第 0 行: →→→→→
第 1 行: ←←←←←
第 2 行: →→→→→
第 3 行: ←←←←←c
// 螺旋遍历：一圈一圈从外向内访问
void spiral_print(int board[ROW][COL])
{
int top = 0, bottom = ROW - 1;
int left = 0, right = COL - 1;
while (top <= bottom && left <= right)
{
// 上边：左 → 右
for (int j = left; j <= right; j++)
printf("%d ", board[top][j]);
top++;
// 右边：上 → 下
for (int i = top; i <= bottom; i++)
printf("%d ", board[i][right]);
right--;
// 下边：右 → 左（如果还有行）
if (top <= bottom) {
for (int j = right; j >= left; j--)
printf("%d ", board[bottom][j]);
bottom--;
}
// 左边：下 → 上（如果还有列）
if (left <= right) {
for (int i = bottom; i >= top; i--)
printf("%d ", board[i][left]);
left++;
}
}
}螺旋遍历路径示意:
→→→→→
↓
→→→→ ↓
↑ ↓ ↓
↑ ←← ↓
↑←←←←←这些遍历模式展示了二维数组操作的多样性——改变遍历顺序是算法设计的基础能力。
5. 随机数生成：rand() 与跨平台确定性
5.1 标准库的 rand() 问题
c
#include <stdlib.h>
#include <stdio.h>
int main(void)
{
srand(42);
printf("%d\n", rand()); // Linux (glibc): 输出某个值
return 0; // Windows (MSVC): 输出不同的值！
}不同平台的 rand() 实现不同——同样的 srand(42) 会给不同序列。这让自动化测试无法通过。
5.2 自定义 LCG（线性同余生成器）
c
static unsigned int seed = 42; // 固定种子
int my_rand(void)
{
// LCG 公式: 使用 glibc 的经典参数，保证跨平台一致
seed = seed * 1103515245 + 12345;
return (seed >> 16) & 0x7FFF; // 返回高 15 位（分布更均匀）
}LCG 的工作原理：每次调用前用乘法+加法更新种子，高位比低位分布更均匀——这就是 (seed >> 16) 的设计。
为什么用经典参数：1103515245 和 12345 是 glibc 中 rand() 的参数——选择它们是因为具有良好的统计性质（周期长、分布均匀）。
5.3 LCG 的数学原理深度解析
LCG 递推公式:
X_{n+1} = (a × X_n + c) mod m
其中:
a = 1103515245 (乘数 multiplier)
c = 12345 (增量 increment)
m = 2^31 (模数 modulus, 32 位有符号整数的一半)
为什么用 >> 16 取高位而不是直接取低 16 位？
低位比特的周期性很强，分布不均匀
高位比特的周期性较弱，统计性质更好
示例 (seed=1):
第 1 次: X1 = (1103515245 × 1 + 12345) mod 2^31 = 1103527590
取高 15 位: 1103527590 >> 16 = 16837
第 2 次: X2 = (1103515245 × 1103527590 + 12345) mod 2^31
取高 15 位: ...验证 LCG 序列的前几项：
c
#include <stdio.h>
static unsigned int seed = 42;
int my_rand(void)
{
seed = seed * 1103515245 + 12345;
printf(" seed = %10u → high bits = %u\n",
seed, (seed >> 16) & 0x7FFF);
return (seed >> 16) & 0x7FFF;
}
int main(void)
{
printf("LCG trace (seed starts at 42):\n");
for (int i = 0; i < 5; i++)
printf("[%d] rand = %d\n", i, my_rand());
return 0;
}输出示例：
LCG trace (seed starts at 42):
seed = 4634763735 → high bits = 70721
[0] rand = 70721
seed = 3525899452 → high bits = 53803
[1] rand = 53803
...5.4 rand() vs my_rand()：跨平台确定性对比
c
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
// 标准库版本——不同平台结果不同！
srand(42);
printf("stdlib: rand() = %d\n", rand());
// 自定义 LCG 版本——所有平台结果一致
unsigned int seed = 42;
seed = seed * 1103515245 + 12345;
printf("my_rand() = %d\n", (seed >> 16) & 0x7FFF);
return 0;
}
// Linux glibc : rand() = 一个值
// macOS BSD libc: rand() = 不同的值
// Windows MSVC : rand() = 又一个不同的值
// 只有 my_rand() 在三者上都输出相同的值！NOTE
LCG 产生的序列完全由 seed 决定——相同 seed 产生相同序列。这正是我们需要的「确定性伪随机」用在回归测试中的原因：保证 exercises.toml 的测试用例能在所有平台上通过，不会因为 rand() 实现不同而导致测试失败。
6. DFS 概念引入：从当前位置出发
6.1 check 函数：DFS 的原子操作
c
int check(int row, int col, dir_t dir)
{
int nr = row + dir.dr; // 计算下一步的行
int nc = col + dir.dc; // 计算下一步的列
if (!is_valid(nr, nc)) // 第一步：检查边界
return 0;
if (chessboard[nr][nc] != 0) // 第二步：检查是否可通行（0 = 可走）
return 0;
return 1; // 可以通过
}这是 DFS 中的单步决策——从当前位置判断某个方向是否可以走。完整的 DFS 会在此基础上递归调用自己继续探索。
6.2 DFS 的递归框架
c
// 检查从 (row, col) 能否到达 (target_row, target_col)
int dfs(int row, int col, int target_row, int target_col)
{
// 终止条件：到达目标
if (row == target_row && col == target_col)
return 1;
// 标记当前位置已访问
visited[row][col] = 1;
// 依次尝试所有方向
for (int i = 0; i < 4; i++)
{
int nr = row + dirs[i].dr;
int nc = col + dirs[i].dc;
if (is_valid(nr, nc) && !visited[nr][nc] && chessboard[nr][nc] == 0)
{
if (dfs(nr, nc, target_row, target_col)) // 递归探索
return 1; // 找到了！
}
}
return 0; // 所有方向都走不通
}虽然本课练习不要求实现完整 DFS（那是课后进阶内容），但 check 和 is_valid 已经为实现 DFS 铺好了基础。
6.3 DFS 迷宫探索的完整追踪
以下用一个 3×3 简单迷宫来手动追踪 DFS 的完整执行过程：
棋盘 (0=路, 1=墙, S=起点, G=终点):
┌───┬───┬───┐
│ S │ 1 │ G │ row 0: 0 1 0
├───┼───┼───┤
│ 0 │ 0 │ 1 │ row 1: 0 0 1
├───┼───┼───┤
│ 1 │ 0 │ 0 │ row 2: 1 0 0
└───┴───┴───┘
DFS 执行追踪 (从 (0,0) 出发，目标 (0,2)):
────────────────────────────────────────
1. dfs(0,0): 标记 visited[0][0]=1
尝试方向 0 (up): (-1,0) → 出界
尝试方向 1 (down): (1,0) = 0, 未访问 → dfs(1,0)
2. dfs(1,0): 标记 visited[1][0]=1
尝试 up: (0,0) 已访问
尝试 down: (2,0) = 1 (墙)
尝试 left: (1,-1) 出界
尝试 right: (1,1) = 0, 未访问 → dfs(1,1)
3. dfs(1,1): 标记 visited[1][1]=1
尝试 up: (0,1) = 1 (墙)
尝试 down: (2,1) = 0, 未访问 → dfs(2,1)
4. dfs(2,1): 标记 visited[2][1]=1
尝试 up: (1,1) 已访问
尝试 down: (3,1) 出界
尝试 left: (2,0) = 1 (墙)
尝试 right: (2,2) = 0, 未访问 → dfs(2,2)
5. dfs(2,2): 标记 visited[2,2]=1
尝试 up: (1,2) = 1 (墙)
尝试 down: (3,2) 出界
尝试 left: (2,1) 已访问
尝试 right: (2,3) 出界
← 四个方向全堵死！
回到 dfs(2,1) → 没有更多方向
回到 dfs(1,1) → 尝试 right: (1,2)=1 (墙)
← 四个方向全试完
回到 dfs(1,0) → 所有方向都试过了
回到 dfs(0,0) → 尝试 right: (0,1)=1 (墙)
← 所有方向都试过了，但从未到达 (0,2)
结果: FAIL — 没有通路！关键观察：DFS 命中死角 (2,2) 后回溯到上一步继续尝试其他方向——这就是「深度优先」的核心：一条道走到黑，走不通就回头。visited 标记防止重复访问已探索的格子。
6.4 DFS vs BFS 初步
| 方面 | DFS (Depth-First) | BFS (Breadth-First) |
|---|---|---|
| 数据结构 | 递归（隐式栈）或显式栈 | 队列 |
| 路径特征 | 找到一条路就返回，不保证最短 | 保证找到最短路径 |
| 内存消耗 | O(深度) — 与迷宫深度成正比 | O(宽度) — 与分支因子成正比 |
| 适用场景 | 存在性判断、全遍历 | 最短路径、分层扩散 |
| 本课中的基础 | check() + is_valid() | 同样的基础，用队列替代递归 |
7. 方向检查的完整流程图
输入 (row, col)
↓
初始化 ways = 0
↓
遍历 dirs[0..3] (up, down, left, right)
↓
对每个方向:
nr = row + dir.dr
nc = col + dir.dc
↓
┌─ is_valid(nr, nc)? ──────→ 否 → continue
│ ↓ 是
└─ chessboard[nr][nc] == 0? → 否 → continue
↓ 是
输出 "direction %s is ok!"
ways++
↓
输出 value 和 ways这个流程图简洁地展示了方格问题中「四个方向 + 双条件判断」的标准范式，后续课程中反复出现。
参考解答
练习1: 棋盘初始化与打印
c
#include <stdio.h>
#define ROW 5
#define COL 5
int chessboard[ROW][COL];
static unsigned int seed = 42;
int my_rand(void)
{
seed = seed * 1103515245 + 12345;
return (seed >> 16) & 0x7FFF;
}
void init_chessboard(void)
{
int i, j;
for (i = 0; i < ROW; i++)
for (j = 0; j < COL; j++)
chessboard[i][j] = my_rand() % 2;
}
void print_chessboard(void)
{
int i, j;
for (i = 0; i < ROW; i++)
{
for (j = 0; j < COL; j++)
printf("%d ", chessboard[i][j]);
printf("\n");
}
}
int main(void)
{
init_chessboard();
print_chessboard();
return 0;
}核心：双层 for 循环遍历 [i][j]。init 在全局数组上直接赋值（无需传参），print 每列元素间用空格分隔，每行末尾换行。
练习2: 方向检查（含完整初始化）
c
#include <stdio.h>
#define ROW 5
#define COL 5
int chessboard[ROW][COL];
static unsigned int seed = 42;
int my_rand(void)
{
seed = seed * 1103515245 + 12345;
return (seed >> 16) & 0x7FFF;
}
void init_chessboard(void)
{
int i, j;
for (i = 0; i < ROW; i++)
for (j = 0; j < COL; j++)
chessboard[i][j] = my_rand() % 2;
}
int is_valid(int row, int col)
{
if (row < 0 || row >= ROW) return 0;
if (col < 0 || col >= COL) return 0;
return 1;
}
struct direction { int dr; int dc; char name[16]; };
typedef struct direction dir_t;
dir_t dirs[4] = {
{-1, 0, "up"},
{ 1, 0, "down"},
{ 0, -1, "left"},
{ 0, 1, "right"},
};
int check(int row, int col, dir_t dir)
{
int nr = row + dir.dr;
int nc = col + dir.dc;
if (!is_valid(nr, nc))
return 0;
if (chessboard[nr][nc] != 0)
return 0;
return 1;
}
int main(void)
{
int row, col, i, ways = 0;
init_chessboard();
scanf("%d %d", &row, &col);
for (i = 0; i < 4; i++)
{
int ret = check(row, col, dirs[i]);
if (ret > 0)
{
printf("direction %s is ok!\n", dirs[i].name);
ways++;
}
}
printf("value = %d\n", chessboard[row][col]);
printf("ways = %d\n", ways);
return 0;
}check 做两件事：边界检查 + 可通行性检查。for 循环依次用四个方向的 dirs[i] 调用 check，成功则输出方向名并计数。全局数组 chessboard 和 dirs 使 main 逻辑极简。
对照检查：二维数组用双层
for了吗？is_valid同时检查了< 0和>= SIZE？check中nr和nc是从row + dir.dr计算的？输出格式用"direction %s is ok!\n"匹配期望输出？
课堂讨论
- dirx 和 diry 用两个独立数组 vs 用
struct direction，哪个在代码可读性上更好？ - 如果要加上左上、左下、右上、右下这 4 个对角线方向，应该如何修改程序（只需改一处）？
- 边界检查中，
row < 0和row >= ROW用||而不是&&连接，为什么？ - 如果用一维数组
int board[ROW * COL]替代二维数组，坐标转换公式是什么？优缺点如何？
讨论答案
Q1: 独立数组 vs struct direction 哪个更好？
struct direction 更好，因为语义聚合更强。
c
// 版本 A: 两个独立数组（可读性差）
int dirx[4] = {-1, 1, 0, 0};
int diry[4] = {0, 0, -1, 1};
// 看这两个数组，无法直观判断 {-1, 0} 是「上」，也无法输出方向名
// 版本 B: 结构体数组（可读性好）
dir_t dirs[4] = {
{-1, 0, "up"},
{ 1, 0, "down"},
{ 0, -1, "left"},
{ 0, 1, "right"},
};结构体的优势：
- 新增字段无痛：加一个
int weight到struct direction，所有方向自动拥有此字段 - 可读性：命名字段
dir.dr比dirx[i]更自文档化 - 调试友好：GDB 中
print dirs[0]能看到{dr=-1, dc=0, name="up"}，而两个独立数组需要手动匹配索引
独立数组的唯一优势是极简场景下的纯粹性——当方向数少（4 个）且不需要方向名时也可以接受。
Q2: 加上 4 个对角线方向只需改哪里？
只需改 dirs[] 数组定义，其余代码完全不动！
c
// 从 4 方向变为 8 方向——只改这一个数组：
dir_t dirs[8] = {
{-1, 0, "up"},
{ 1, 0, "down"},
{ 0, -1, "left"},
{ 0, 1, "right"},
{-1, -1, "up-left"},
{-1, 1, "up-right"},
{ 1, -1, "down-left"},
{ 1, 1, "down-right"},
};
// main 中的循环需要改一处上界
for (i = 0; i < 8; i++) // 4 → 8
{
int ret = check(row, col, dirs[i]); // 这行完全不需要变
// ...
}改了两处但逻辑框架零改动——这正是方向数组作为数据驱动设计的威力。
Q3: 越界检查为什么用 || 而不是 &&？
因为越界有两种情况，发生任何一种都不合法。
c
// 正确写法：
if (row < 0 || row >= ROW) // 小于 0 或 大于等于上限 → 越界
return 0;
// 错误写法：
if (row < 0 && row >= ROW) // 同时小于 0 且大于等于上限 → 永不成立！
return 0;row 不能同时小于 0 又大于等于 ROW——逻辑上不可能。所以用 ||（或）来表示「任何一种越界情况发生即判定为非法」。这是防御性编程的基本思维：列出所有不允许的情况，任一触发即拒绝。
Q4: 一维数组模拟二维数组？
坐标转换公式：board[row][col] → board[row * COL + col]
c
#define ROW 5
#define COL 5
// 二维数组版本
int board_2d[ROW][COL];
board_2d[2][3] = 1;
// 等价的一维数组版本
int board_1d[ROW * COL]; // 25 个元素
board_1d[2 * COL + 3] = 1; // 等价于 board_2d[2][3]对比：
| 方面 | 二维数组 board[ROW][COL] | 一维数组 board[ROW * COL] |
|---|---|---|
| 语法可读性 | board[i][j] 直观 | board[i*COL+j] 需心算 |
| 内存布局 | Row-Major 自动 | 同 Row-Major，自己计算偏移 |
| 传递函数 | 必须知道 COL | 只需首地址 + 总大小 |
| 动态分配 | malloc(ROW*sizeof(int*)) 复杂 | malloc(ROW*COL*sizeof(int)) 简洁 |
| 适用场景 | 固定大小的局部棋盘 | 动态大小的棋盘、简化传参 |
一维数组在动态分配和通用函数设计时有优势；二维数组在语义清晰度上有优势。本课选二维数组是因为棋盘大小固定为 5×5。
课后练习
杨辉三角形：打印杨辉三角形的前 10 行。每个数等于它上方两数之和，用二维数组存储。
知识点提示：二维数组
a[10][10]存储、递推公式a[i][j] = a[i-1][j-1] + a[i-1][j]、三角形边界初始化为 1棋盘计数 BFS：从
(0, 0)出发 BFS 遍历一个全 0 棋盘，统计从起点能到达多少个格子（四方向）。知识点提示：方向数组遍历、visited 标记数组、BFS 队列或 DFS 递归
8 皇后计数：在一个 8×8 的棋盘上放置 8 个皇后，使其互不攻击，统计共有多少种合法放置方案。
知识点提示：回溯 DFS、冲突判断（同行/同列/对角线）、递归 + 全局计数器
练习1: 杨辉三角形
c
#include <stdio.h>
#define N 10
int main(void)
{
int a[N][N] = {{0}};
int i, j;
// 第一列和对角线初始化为 1
for (i = 0; i < N; i++)
{
a[i][0] = 1; // 每行第一列
a[i][i] = 1; // 对角线
}
// 递推填充：a[i][j] = a[i-1][j-1] + a[i-1][j]
for (i = 2; i < N; i++)
for (j = 1; j < i; j++)
a[i][j] = a[i-1][j-1] + a[i-1][j];
// 打印三角形
for (i = 0; i < N; i++)
{
for (j = 0; j <= i; j++)
printf("%4d", a[i][j]);
printf("\n");
}
return 0;
}杨辉三角的递推关系 C(n,k) = C(n-1,k-1) + C(n-1,k) 直接在二维数组上实现。每行只打印到 j <= i（三角形）。
练习2: DFS 可达性统计
c
#include <stdio.h>
#define ROW 5
#define COL 5
int board[ROW][COL];
int visited[ROW][COL];
int dirx[4] = {-1, 1, 0, 0};
int diry[4] = {0, 0, -1, 1};
int count = 0;
void dfs(int row, int col)
{
visited[row][col] = 1;
count++;
for (int i = 0; i < 4; i++)
{
int nr = row + dirx[i];
int nc = col + diry[i];
if (nr >= 0 && nr < ROW && nc >= 0 && nc < COL
&& !visited[nr][nc] && board[nr][nc] == 0)
{
dfs(nr, nc); // 递归探索
}
}
}
int main(void)
{
dfs(0, 0);
printf("reachable = %d\n", count);
return 0;
}从起点递归地探索所有相邻的可行走格子，visited 防止重复访问。这是 BFS/DFS 经典框架——之后在词法分析器（Lesson 21）中也会用到类似模式。
练习3: 8 皇后计数
c
#include <stdio.h>
#include <stdlib.h>
#define N 8
int board[N]; // board[row] = col —— 用一维数组表示皇后位置
int total = 0;
// 检查在第 row 行第 col 列放置皇后是否安全
int is_safe(int row, int col)
{
for (int r = 0; r < row; r++)
{
if (board[r] == col) // 同列冲突
return 0;
if (abs(board[r] - col) == abs(r - row)) // 对角线冲突
return 0;
}
return 1;
}
void solve(int row)
{
if (row == N) // 8 行全部放置完毕
{
total++;
return;
}
for (int col = 0; col < N; col++)
{
if (is_safe(row, col))
{
board[row] = col;
solve(row + 1); // 递归到下一行
}
}
}
int main(void)
{
solve(0);
printf("total = %d\n", total); // 输出 92
return 0;
}经典回溯问题——solve(row) 尝试在第 row 行的每一列放置皇后，is_safe 检查与之前所有行的冲突。对角线冲突用 abs(r1-r2) == abs(c1-c2) 判定（回顾 Lesson 07 课后练习的皇后攻击范围）。
参考资料
- ISO C99 Standard, Section 6.5.2.1 — 多维数组的下标与存储布局
- Linear Congruential Generator — LCG 伪随机数生成器的数学原理与参数选择
- The C Programming Language, Section 5.7 — Kernighan & Ritchie 对多维数组作为函数参数的讲解
- Eight Queens Puzzle — 经典回溯算法问题与 92 种解法
"Make it work, make it right, make it fast." — Kent Beck