一、题目描述有一个N×N 的棋盘由黑格子用1表示和白格子用0表示组成。棋子在棋盘上可以上下左右移动但必须遵循以下规则只能从黑色格走到相邻的白色格或者从白色格走到相邻的黑色格即相邻的两个格子颜色必须不同才能移动任务对于给定的棋盘和 M 个查询每个查询给出一个起始坐标(i,j) 请计算从该格子开始能移动到的所有格子总数包含起始格本身。输入描述第一行两个正整数表示nm。下面n行每行n个字符字符是1或0分别表示黑格子和白格子字符之间无空格。接下来m行每行两个数ij用空格隔开表示棋盘的第行第列的格子需要计算该棋子从该格子的移动范围是多少格。输出描述m行每行一个数表示每个询问的答案。补充说明对于全部的测试点保证1≤n≤10001≤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. 问题建模图论视角我们可以将棋盘看作一个无向图节点棋盘的每一个格子 (r,c) 。边如果两个相邻格子上下左右颜色不同则它们之间存在一条边。目标求某个节点所在的连通分量Connected Component的大小。2. 为什么暴力法会超时最直观的想法是对于每一个查询 (i,j)都运行一次 BFS 或 DFS 来统计可达格子数。单次 BFS 复杂度 O(N2) 最坏情况遍历全图。总复杂度 O(M⋅N2) 。数据爆炸当 N1000,M10000 时运算量高达 10^10 级别。在 C 中通常 11 秒只能处理约 10^8 次运算这会导致严重的TLE (Time Limit Exceeded)。3. 核心优化预处理连通分量观察发现棋盘是静态的连通分量的结构不会随查询改变。策略我们只需要在读取完棋盘后一次性遍历整个棋盘。步骤维护一个visited数组和一个answer[N][N]结果数组。双重循环遍历每个格子 (i,j) 。如果 (i,j) 未被访问启动一次 BFS/DFS找出该连通分量内的所有格子坐标存入临时列表。统计该分量的大小 S 。关键一步将列表中所有格子的answer值统一设为 S 。处理查询时直接 O(1) 输出answer[i][j]。优化后复杂度预处理每个格子最多进队出队一次 O(N2) 。查询 MM 次 O(1) 查表 O(M)。总复杂度 O(N2M) 完美通过三、C 代码实现本代码采用了标准的 C11/14 写法使用了vector动态数组和queue队列并开启了 IO 加速以应对大数据量输入。#include iostream #include vector #include string #include queue using namespace std; // 全局变量定义避免大数组在栈上溢出 int n, m; vectorstring board; // 存储棋盘 vectorvectorint resultGrid; // 记忆化结果resultGrid[i][j] 存储该点的连通块大小 vectorvectorbool visited; // 访问标记 // 方向数组上、下、左、右 const int dx[] {-1, 1, 0, 0}; const int dy[] {0, 0, -1, 1}; // 坐标结构体 struct Point { int x, y; }; /** * brief BFS 遍历当前连通分量并填充结果 * param startX 起始行索引 (0-based) * param startY 起始列索引 (0-based) */ void bfs(int startX, int startY) { queuePoint q; vectorPoint component; // 暂存当前连通分量中的所有坐标 // 初始化 q.push({startX, startY}); visited[startX][startY] true; component.push_back({startX, startY}); char startColor board[startX][startY]; while (!q.empty()) { Point cur q.front(); q.pop(); 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]; // 1. 边界检查 if (nx 0 nx n ny 0 ny n) { // 2. 核心规则未访问 且 颜色必须不同 if (!visited[nx][ny] board[nx][ny] ! currentColor) { visited[nx][ny] true; q.push({nx, ny}); component.push_back({nx, ny}); } } } } // 【关键优化】将该连通分量的大小赋值给分量内的所有格子 int size component.size(); for (const auto p : component) { resultGrid[p.x][p.y] size; } } int main() { // 关闭同步流加速 C 输入输出 (必做防止 IO 超时) ios::sync_with_stdio(false); cin.tie(nullptr); if (!(cin n m)) return 0; // 初始化容器 board.resize(n); resultGrid.assign(n, vectorint(n, 0)); visited.assign(n, vectorbool(n, false)); // 读取棋盘数据 for (int i 0; i n; i) { cin board[i]; } // --- 预处理阶段 --- // 遍历每一个格子如果未访问则它是一个新连通分量的起点 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; cin r c; // 注意题目输入是从 1 开始数组索引从 0 开始需减 1 cout resultGrid[r - 1][c - 1] \n; } return 0; }四、代码关键点解析1. IO 加速ios::sync_with_stdio(false); cin.tie(nullptr);在 N1000,M10000 的情况下输入输出数据量较大。默认的cin/cout会与 C 标准 IO 同步速度较慢。加上这两行代码可以显著提升性能避免因为 IO 慢而超时。2. 记忆化填表在bfs函数末尾int size component.size(); for (const auto p : component) { resultGrid[p.x][p.y] size; }这是本题的精髓。传统的 BFS 只返回当前起点的结果而这里我们将整个连通块的结果都算出来并存好。这样后续如果有查询落在同一个连通块的其他位置直接查表即可无需再次搜索。3. 状态判断逻辑if (!visited[nx][ny] board[nx][ny] ! currentColor)!visited保证不重复访问防止死循环。! currentColor严格遵循题目“黑白交替”的规则。只有颜色不同才能走。4. 坐标转换题目输入的坐标 (i,j) 是1-based从1开始计数而 C 数组是0-based。cout resultGrid[r - 1][c - 1] \n;务必记得-1否则会发生数组越界或答案错误。五、复杂度分析指标分析结果时间复杂度预处理阶段每个节点最多入队出队一次 (O(N2))查询阶段 MM 次常数时间操作 (O(M))。O(N2M)空间复杂度需要存储棋盘、访问数组、结果数组以及 BFS 队列/列表均为 N×N 级别。O(N2)在 N1000 时 N^210^6 完全在内存限制和时间限制的安全范围内。六、常见坑点与避坑指南⚠️递归爆栈如果使用 DFS 递归实现当连通分量很大如接近10^6 时可能会导致栈溢出Stack Overflow。建议使用 BFS队列实现或 非递归 DFS。多次重复搜索如果没有visited数组或者没有在预处理中将结果填入resultGrid而是对每个查询单独跑 BFS必然超时。输入坐标未减 1这是新手最容易犯的错误导致访问resultGrid[1000][1000]越界。字符读取问题读取棋盘时每一行是一个字符串不要试图用cin char循环 NN 次忽略换行符直接用cin string最稳妥。七、总结这道题是典型的“静态图多源查询”模型。核心思想空间换时间通过一次全图遍历解决所有潜在查询。考察点BFS/DFS 图遍历、连通分量、数组映射、IO 优化。适用场景类似的问题还有“岛屿数量”、“洪水填充”、“朋友圈大小”等掌握此模板可举一反三。希望这篇题解能帮助你彻底攻克此类机考题如果觉得有用欢迎点赞、收藏、关注后续将持续更新更多大厂算法真题解析
【华为OD机试真题】黑白棋 · N×N棋盘移动范围问题（C++）
发布时间：2026/6/25 20:08:20
一、题目描述有一个N×N 的棋盘由黑格子用1表示和白格子用0表示组成。棋子在棋盘上可以上下左右移动但必须遵循以下规则只能从黑色格走到相邻的白色格或者从白色格走到相邻的黑色格即相邻的两个格子颜色必须不同才能移动任务对于给定的棋盘和 M 个查询每个查询给出一个起始坐标(i,j) 请计算从该格子开始能移动到的所有格子总数包含起始格本身。输入描述第一行两个正整数表示nm。下面n行每行n个字符字符是1或0分别表示黑格子和白格子字符之间无空格。接下来m行每行两个数ij用空格隔开表示棋盘的第行第列的格子需要计算该棋子从该格子的移动范围是多少格。输出描述m行每行一个数表示每个询问的答案。补充说明对于全部的测试点保证1≤n≤10001≤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. 问题建模图论视角我们可以将棋盘看作一个无向图节点棋盘的每一个格子 (r,c) 。边如果两个相邻格子上下左右颜色不同则它们之间存在一条边。目标求某个节点所在的连通分量Connected Component的大小。2. 为什么暴力法会超时最直观的想法是对于每一个查询 (i,j)都运行一次 BFS 或 DFS 来统计可达格子数。单次 BFS 复杂度 O(N2) 最坏情况遍历全图。总复杂度 O(M⋅N2) 。数据爆炸当 N1000,M10000 时运算量高达 10^10 级别。在 C 中通常 11 秒只能处理约 10^8 次运算这会导致严重的TLE (Time Limit Exceeded)。3. 核心优化预处理连通分量观察发现棋盘是静态的连通分量的结构不会随查询改变。策略我们只需要在读取完棋盘后一次性遍历整个棋盘。步骤维护一个visited数组和一个answer[N][N]结果数组。双重循环遍历每个格子 (i,j) 。如果 (i,j) 未被访问启动一次 BFS/DFS找出该连通分量内的所有格子坐标存入临时列表。统计该分量的大小 S 。关键一步将列表中所有格子的answer值统一设为 S 。处理查询时直接 O(1) 输出answer[i][j]。优化后复杂度预处理每个格子最多进队出队一次 O(N2) 。查询 MM 次 O(1) 查表 O(M)。总复杂度 O(N2M) 完美通过三、C 代码实现本代码采用了标准的 C11/14 写法使用了vector动态数组和queue队列并开启了 IO 加速以应对大数据量输入。#include iostream #include vector #include string #include queue using namespace std; // 全局变量定义避免大数组在栈上溢出 int n, m; vectorstring board; // 存储棋盘 vectorvectorint resultGrid; // 记忆化结果resultGrid[i][j] 存储该点的连通块大小 vectorvectorbool visited; // 访问标记 // 方向数组上、下、左、右 const int dx[] {-1, 1, 0, 0}; const int dy[] {0, 0, -1, 1}; // 坐标结构体 struct Point { int x, y; }; /** * brief BFS 遍历当前连通分量并填充结果 * param startX 起始行索引 (0-based) * param startY 起始列索引 (0-based) */ void bfs(int startX, int startY) { queuePoint q; vectorPoint component; // 暂存当前连通分量中的所有坐标 // 初始化 q.push({startX, startY}); visited[startX][startY] true; component.push_back({startX, startY}); char startColor board[startX][startY]; while (!q.empty()) { Point cur q.front(); q.pop(); 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]; // 1. 边界检查 if (nx 0 nx n ny 0 ny n) { // 2. 核心规则未访问 且 颜色必须不同 if (!visited[nx][ny] board[nx][ny] ! currentColor) { visited[nx][ny] true; q.push({nx, ny}); component.push_back({nx, ny}); } } } } // 【关键优化】将该连通分量的大小赋值给分量内的所有格子 int size component.size(); for (const auto p : component) { resultGrid[p.x][p.y] size; } } int main() { // 关闭同步流加速 C 输入输出 (必做防止 IO 超时) ios::sync_with_stdio(false); cin.tie(nullptr); if (!(cin n m)) return 0; // 初始化容器 board.resize(n); resultGrid.assign(n, vectorint(n, 0)); visited.assign(n, vectorbool(n, false)); // 读取棋盘数据 for (int i 0; i n; i) { cin board[i]; } // --- 预处理阶段 --- // 遍历每一个格子如果未访问则它是一个新连通分量的起点 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; cin r c; // 注意题目输入是从 1 开始数组索引从 0 开始需减 1 cout resultGrid[r - 1][c - 1] \n; } return 0; }四、代码关键点解析1. IO 加速ios::sync_with_stdio(false); cin.tie(nullptr);在 N1000,M10000 的情况下输入输出数据量较大。默认的cin/cout会与 C 标准 IO 同步速度较慢。加上这两行代码可以显著提升性能避免因为 IO 慢而超时。2. 记忆化填表在bfs函数末尾int size component.size(); for (const auto p : component) { resultGrid[p.x][p.y] size; }这是本题的精髓。传统的 BFS 只返回当前起点的结果而这里我们将整个连通块的结果都算出来并存好。这样后续如果有查询落在同一个连通块的其他位置直接查表即可无需再次搜索。3. 状态判断逻辑if (!visited[nx][ny] board[nx][ny] ! currentColor)!visited保证不重复访问防止死循环。! currentColor严格遵循题目“黑白交替”的规则。只有颜色不同才能走。4. 坐标转换题目输入的坐标 (i,j) 是1-based从1开始计数而 C 数组是0-based。cout resultGrid[r - 1][c - 1] \n;务必记得-1否则会发生数组越界或答案错误。五、复杂度分析指标分析结果时间复杂度预处理阶段每个节点最多入队出队一次 (O(N2))查询阶段 MM 次常数时间操作 (O(M))。O(N2M)空间复杂度需要存储棋盘、访问数组、结果数组以及 BFS 队列/列表均为 N×N 级别。O(N2)在 N1000 时 N^210^6 完全在内存限制和时间限制的安全范围内。六、常见坑点与避坑指南⚠️递归爆栈如果使用 DFS 递归实现当连通分量很大如接近10^6 时可能会导致栈溢出Stack Overflow。建议使用 BFS队列实现或 非递归 DFS。多次重复搜索如果没有visited数组或者没有在预处理中将结果填入resultGrid而是对每个查询单独跑 BFS必然超时。输入坐标未减 1这是新手最容易犯的错误导致访问resultGrid[1000][1000]越界。字符读取问题读取棋盘时每一行是一个字符串不要试图用cin char循环 NN 次忽略换行符直接用cin string最稳妥。七、总结这道题是典型的“静态图多源查询”模型。核心思想空间换时间通过一次全图遍历解决所有潜在查询。考察点BFS/DFS 图遍历、连通分量、数组映射、IO 优化。适用场景类似的问题还有“岛屿数量”、“洪水填充”、“朋友圈大小”等掌握此模板可举一反三。希望这篇题解能帮助你彻底攻克此类机考题如果觉得有用欢迎点赞、收藏、关注后续将持续更新更多大厂算法真题解析
