【华为OD机试真题】黑白棋 · N×N棋盘移动范围问题（C语言）

一、题目描述有一个 N×NN×N 的棋盘由黑格子用1表示和白格子用0表示组成。棋子在棋盘上可以上下左右移动但必须遵循以下规则只能从黑色格走到相邻的白色格或者从白色格走到相邻的黑色格即相邻的两个格子颜色必须不同才能移动任务对于给定的棋盘和 MM 个查询每个查询给出一个起始坐标 (i,j)(i,j) 请计算从该格子开始能移动到的所有格子总数包含起始格本身。输入描述第一行两个正整数表示nm。下面n行每行n个字符字符是1或0分别表示黑格子和白格子字符之间无空格。接下来m行每行两个数ij用空格隔开表示棋盘的第行第列的格子需要计算该棋子从该格子的移动范围是多少格。输出描述m行每行一个数表示每个询问的答案。补充说明对于全部的测试点保证1≤n≤10001≤m≤10000。数据范围1≤n≤10001≤n≤10001≤m≤100001≤m≤10000示例1输入2 1 01 10 2 2输出4示例2输入3 3 001 111 001 1 1 2 2 2 3输出3 5 1(解释2x2棋盘(2,2)是0它可以走到(2,1)1(1,2)1进而走到(1,1)0所有4个格子互通)二、解题思路1. 为什么不能对每个查询单独做 BFS单次 BFS 最坏遍历全图 O(N^2)O(N^2) 。MM 次查询总耗时 O(M⋅N^2)≈104×1061010O(M⋅N^2)≈104×1061010 次操作。后果C 语言虽然快但也无法在 1 秒内完成 10101010 次运算必然TLE (超时)。2. 优化方案预处理 染色法棋盘是静态的连通块结构不变。策略在读取完棋盘后立即遍历所有格子。执行遇到未访问的格子启动 BFS 找出其所属的整个连通块。统计该块的大小 SS 。关键步骤将该块内所有格子的答案直接记录为 SS 相当于给这个连通块“染色”并标记数值。查询对于 MM 个询问直接查表输出耗时 O(1)O(1) 。总复杂度 O(N2M)O(N2M) 轻松 AC。3. C 语言实现的特殊性无 STLC 语言没有std::queue和std::vector。解决方案使用大数组模拟队列循环队列或简单指针队列。使用结构体数组暂存当前连通块的坐标以便最后统一赋值。使用静态全局数组避免栈溢出1000×10001000×1000 的数组在栈上会爆需放在全局区或堆区。三、C 语言代码实现本代码完全遵循 C99 标准不依赖任何 C 特性适合在严格限制语言的机考环境中使用。#include stdio.h #include stdlib.h #include string.h #include stdbool.h // 定义最大尺寸根据题目 N1000 #define MAXN 1005 // 全局变量分配在大内存区防止栈溢出 char board[MAXN][MAXN]; // 棋盘 int resultGrid[MAXN][MAXN]; // 结果缓存表 bool visited[MAXN][MAXN]; // 访问标记 int n, m; // 方向数组上、下、左、右 const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; // 坐标结构体 typedef struct { int x; int y; } Point; // 手动实现队列所需的数组 // 最大可能入队元素为 N*N Point queue[MAXN * MAXN]; /** * brief 使用 BFS 寻找连通分量并填充结果 * param startX 起始行 (0-based) * param startY 起始列 (0-based) */ void bfs(int startX, int startY) { int head 0; int tail 0; // 临时数组用于存储当前连通分量的所有坐标以便最后统一赋值 // 极端情况下可能包含所有格子 static Point component[MAXN * MAXN]; int compSize 0; // 初始化队列 queue[tail] (Point){startX, startY}; visited[startX][startY] true; component[compSize] (Point){startX, startY}; char startColor board[startX][startY]; while (head tail) { Point cur queue[head]; int cx cur.x; int cy cur.y; char currentColor board[cx][cy]; // 遍历四个方向 for (int i 0; i 4; i) { int nx cx dx[i]; int ny cy dy[i]; // 边界检查 if (nx 0 nx n ny 0 ny n) { // 核心逻辑未访问 且 颜色不同 if (!visited[nx][ny] board[nx][ny] ! currentColor) { visited[nx][ny] true; queue[tail] (Point){nx, ny}; component[compSize] (Point){nx, ny}; } } } } // 将当前连通分量的大小赋值给该分量内的所有格子 for (int i 0; i compSize; i) { resultGrid[component[i].x][component[i].y] compSize; } } int main() { // 优化输入输出速度 // 在 C 语言中scanf/printf 通常足够快但若数据量极大可考虑 getchar 快速读入 // 此处使用标准 scanf 即可满足 1s 时限 if (scanf(%d %d, n, m) ! 2) return 0; // 读取棋盘 // 注意每行是一个字符串中间无空格 for (int i 0; i n; i) { scanf(%s, board[i]); } // 初始化 visited 和 resultGrid (全局变量默认为 0/false但显式初始化更安全) // 由于是全局变量实际上已经初始化为 0 和 false此步可省略以节省时间 // memset(visited, 0, sizeof(visited)); // --- 预处理阶段 --- for (int i 0; i n; i) { for (int j 0; j n; j) { if (!visited[i][j]) { bfs(i, j); } } } // --- 查询阶段 --- for (int k 0; k m; k) { int r, c; scanf(%d %d, r, c); // 题目坐标从 1 开始转换为 0-based printf(%d\n, resultGrid[r - 1][c - 1]); } return 0; }四、代码深度解析1. 手动模拟队列C 语言没有现成的队列库。我们定义了一个全局结构体数组Point queue[MAXN * MAXN]并使用head和tail两个指针来模拟入队tail和出队head操作。优点避免了动态内存分配malloc/free的开销速度极快。注意队列大小必须开得足够大 N2N2 因为在最坏情况下全盘连通所有格子都会进入队列。2. 连通分量暂存数组static Point component[MAXN * MAXN];在bfs函数内部我们需要知道哪些格子属于当前这个连通块以便最后统一填入resultGrid。这里使用了一个静态数组来暂存这些坐标。为什么用static避免每次调用bfs都在栈上重新分配巨大的数组空间防止栈溢出。3. 全局数组 vs 局部数组char board[MAXN][MAXN]; // 全局1000×10001000×1000 的char数组占用约 1MBint数组占用 4MB。如果在main函数内定义这些大数组可能会超过默认栈大小Windows 通常 1MB-2MBLinux 通常 8MB导致Segmentation Fault。最佳实践在算法竞赛和机考中大数组务必定义为全局变量。4. 输入处理scanf(%s, board[i]);题目描述中字符之间无空格每行是一个连续的字符串。使用%s可以直接读取一行自动忽略前导空白符并直到遇到换行符停止非常适合此类棋盘输入。五、复杂度与性能分析指标分析结论时间复杂度预处理遍历全图一次 O(N^2)O(N^2) 查询 MM 次 O(1)O(1) 。O(N^2M)O(N^2M)空间复杂度棋盘、结果表、访问标记、队列、暂存数组均为 O(N^2)O(N^2) 。O(N^2)O(N^2)内存占用约 5×1000×1000×45×1000×1000×4 字节 ≈20≈20 MB。远低于常见 256MB 限制运行效率纯 C 实现无虚函数、无动态扩容常数项极小。极速六、避坑指南⚠️栈溢出Stack Overflow❌ 错误在main或bfs中定义int visited[1000][1000]。✅ 正确定义为全局变量或使用malloc动态分配。数组越界题目坐标从 1 开始C 数组从 0 开始。务必执行r-1,c-1。队列数组大小要开到 N×N 不要只开 N 。字符读取陷阱如果使用scanf( %c, ch)逐个字符读取需要注意跳过换行符。直接使用scanf(%s, str)读取整行字符串更简单且不易出错。初始化问题全局变量自动初始化为 0 或false。如果是在多组测试用例While(scanf...)的场景下记得每次循环前用memset清空数组。本题描述似为单组数据故可省略。七、总结这道题是考察图论基础与工程优化能力的经典题目。对于 C 语言使用者它考验了手动实现数据结构队列的能力。对于算法思维它强调了预处理和空间换时间的重要性。掌握这套“BFS 连通分量预处理 手动队列”的模板不仅能解决此题还能应对“岛屿数量”、“洪水填充”、“最大连通域”等一系列变种问题。希望这篇博文能为你的机考备战提供强有力的支持如果觉得有用欢迎点赞、收藏、关注更多 C/C 算法干货持续更新中