一、题目描述有一个 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. 核心观察图论建模这道题本质上是一个图的遍历问题。将棋盘的每一个格子看作图中的一个节点。如果两个相邻格子上下左右颜色不同则在这两个节点之间连一条无向边。题目要求的“移动范围”实际上就是求起始节点所在的连通分量Connected Component的大小。2. 为什么不能每次查询都 BFS如果对于每个查询 (i,j)(i,j) 都单独进行一次 BFS/DFS时间复杂度为 O(M⋅N2)O(M⋅N2) 。根据数据范围 N1000,M10000N1000,M10000 最坏情况下运算量约为 10101010 这会导致超时TLE。3. 优化策略预处理连通分量由于棋盘是静态的连通分量的结构不会改变。我们可以采用空间换时间的策略预处理阶段遍历整个棋盘对每个未访问过的格子启动一次 BFS/DFS。找出该格子所属的整个连通分量。统计该分量的大小 SS 。将该分量内所有格子的答案都标记为 SS 。查询阶段对于每个查询 (i,j)(i,j) 直接 O(1)O(1) 返回预处理好的结果。总时间复杂度 O(N2)O(N2) (预处理) O(M)O(M) (查询) O(N2M)O(N2M)完全满足时限要求。三、算法步骤️读取输入解析 N,MN,M 和棋盘矩阵。注意字符0和1的处理。初始化visited[N][N]标记格子是否已被访问。result[N][N]存储每个格子所属连通分量的大小。遍历预处理双重循环遍历每个格子 (i,j)(i,j) 。如果!visited[i][j]启动 BFS使用队列进行广度优先搜索。收集当前连通分量中的所有坐标。搜索条件相邻且在边界内、未访问、颜色与当前格子不同。搜索结束后将收集到的所有坐标在result数组中赋值为本次搜索的节点总数。处理查询读取 mm 组坐标注意题目坐标从 1 开始需转换为 0-based 索引。直接输出result[r][c]。四、Code实现1. Java 实现Java 版本使用了Queue和ArrayList来管理 BFS 过程代码结构清晰适合面向对象思维。import java.util.*; import java.io.*; public class Main { static int n, m; static char[][] board; static int[][] result; // 存储每个格子的答案 static boolean[][] visited; // 方向数组上下左右 static int[] dx {0, 0, 1, -1}; static int[] dy {1, -1, 0, 0}; public static void main(String[] args) { Scanner sc new Scanner(System.in); if (!sc.hasNext()) return; n sc.nextInt(); m sc.nextInt(); board new char[n][n]; result new int[n][n]; visited new boolean[n][n]; // 读取棋盘 for (int i 0; i n; i) { String line sc.next(); for (int j 0; j n; j) { board[i][j] line.charAt(j); } } // 核心预处理所有连通分量 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 sc.nextInt() - 1; // 转为0-based int c sc.nextInt() - 1; System.out.println(result[r][c]); } } // BFS 寻找连通分量并填充结果 static void bfs(int startR, int startC) { Queueint[] queue new LinkedList(); Listint[] component new ArrayList(); // 记录当前分量包含的所有格子 queue.offer(new int[]{startR, startC}); visited[startR][startC] true; component.add(new int[]{startR, startC}); while (!queue.isEmpty()) { int[] cur queue.poll(); int r cur[0]; int c cur[1]; char currentColor board[r][c]; for (int d 0; d 4; d) { int nr r dx[d]; int nc c dy[d]; // 检查边界、未访问、颜色不同 if (nr 0 nr n nc 0 nc n !visited[nr][nc] board[nr][nc] ! currentColor) { visited[nr][nc] true; queue.offer(new int[]{nr, nc}); component.add(new int[]{nr, nc}); } } } // 将该连通分量的大小赋值给分量内的所有格子 int size component.size(); for (int[] cell : component) { result[cell[0]][cell[1]] size; } } }2. Go 语言实现Go 版本利用切片模拟队列内存控制更灵活执行效率极高非常适合处理大规模数据。package main import ( bufio fmt os ) var ( n, m int board [][]byte result [][]int visited [][]bool dx []int{0, 0, 1, -1} dy []int{1, -1, 0, 0} ) func main() { // 使用 bufio 提高读取效率 scanner : bufio.NewScanner(os.Stdin) if !scanner.Scan() { return } fmt.Sscanf(scanner.Text(), %d %d, n, m) board make([][]byte, n) result make([][]int, n) visited make([][]bool, n) for i : 0; i n; i { scanner.Scan() line : scanner.Text() board[i] []byte(line) result[i] make([]int, n) visited[i] make([]bool, n) } // 预处理所有连通分量 for i : 0; i n; i { for j : 0; j n; j { if !visited[i][j] { bfs(i, j) } } } // 处理查询 for k : 0; k m; k { if !scanner.Scan() { break } var r, c int fmt.Sscanf(scanner.Text(), %d %d, r, c) // 坐标转换 fmt.Println(result[r-1][c-1]) } } func bfs(startR, startC int) { // 使用切片模拟队列 queue : [][2]int{{startR, startC}} component : [][2]int{{startR, startC}} visited[startR][startC] true head : 0 for head len(queue) { r, c : queue[head][0], queue[head][1] head currentColor : board[r][c] for d : 0; d 4; d { nr, nc : rdx[d], cdy[d] // 核心判断边界 未访问 颜色不同 if nr 0 nr n nc 0 nc n !visited[nr][nc] board[nr][nc] ! currentColor { visited[nr][nc] true queue append(queue, [2]int{nr, nc}) component append(component, [2]int{nr, nc}) } } } // 填充结果 size : len(component) for _, cell : range component { result[cell[0]][cell[1]] size } }五、复杂度分析指标分析结论时间复杂度预处理阶段每个格子最多进队出队一次耗时 O(N2)O(N2) 查询阶段 MM 次操作每次 O(1)O(1) 。O(N2M)O(N2M)空间复杂度需要存储棋盘、访问标记数组、结果数组以及 BFS 队列/列表。O(N2)O(N2)在 N1000,M10000N1000,M10000 的数据规模下运算量约为 106106 级别远低于一般机考 108108 的每秒限制能够轻松 AC。总结本题是典型的“静态图多源查询”问题。关键点识别出“颜色交替”即为图的边并将多次查询转化为一次全图遍历。技巧在 BFS 过程中暂存连通分量内的所有节点遍历结束后统一赋值避免了重复计算。希望这篇题解能帮助你掌握这类问题如果觉得有用欢迎点赞、收藏、关注后续将带来更多od机考真题解析
【华为OD机试真题】黑白棋 · N×N棋盘移动范围问题（Java/Go）
一、题目描述有一个 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. 核心观察图论建模这道题本质上是一个图的遍历问题。将棋盘的每一个格子看作图中的一个节点。如果两个相邻格子上下左右颜色不同则在这两个节点之间连一条无向边。题目要求的“移动范围”实际上就是求起始节点所在的连通分量Connected Component的大小。2. 为什么不能每次查询都 BFS如果对于每个查询 (i,j)(i,j) 都单独进行一次 BFS/DFS时间复杂度为 O(M⋅N2)O(M⋅N2) 。根据数据范围 N1000,M10000N1000,M10000 最坏情况下运算量约为 10101010 这会导致超时TLE。3. 优化策略预处理连通分量由于棋盘是静态的连通分量的结构不会改变。我们可以采用空间换时间的策略预处理阶段遍历整个棋盘对每个未访问过的格子启动一次 BFS/DFS。找出该格子所属的整个连通分量。统计该分量的大小 SS 。将该分量内所有格子的答案都标记为 SS 。查询阶段对于每个查询 (i,j)(i,j) 直接 O(1)O(1) 返回预处理好的结果。总时间复杂度 O(N2)O(N2) (预处理) O(M)O(M) (查询) O(N2M)O(N2M)完全满足时限要求。三、算法步骤️读取输入解析 N,MN,M 和棋盘矩阵。注意字符0和1的处理。初始化visited[N][N]标记格子是否已被访问。result[N][N]存储每个格子所属连通分量的大小。遍历预处理双重循环遍历每个格子 (i,j)(i,j) 。如果!visited[i][j]启动 BFS使用队列进行广度优先搜索。收集当前连通分量中的所有坐标。搜索条件相邻且在边界内、未访问、颜色与当前格子不同。搜索结束后将收集到的所有坐标在result数组中赋值为本次搜索的节点总数。处理查询读取 mm 组坐标注意题目坐标从 1 开始需转换为 0-based 索引。直接输出result[r][c]。四、Code实现1. Java 实现Java 版本使用了Queue和ArrayList来管理 BFS 过程代码结构清晰适合面向对象思维。import java.util.*; import java.io.*; public class Main { static int n, m; static char[][] board; static int[][] result; // 存储每个格子的答案 static boolean[][] visited; // 方向数组上下左右 static int[] dx {0, 0, 1, -1}; static int[] dy {1, -1, 0, 0}; public static void main(String[] args) { Scanner sc new Scanner(System.in); if (!sc.hasNext()) return; n sc.nextInt(); m sc.nextInt(); board new char[n][n]; result new int[n][n]; visited new boolean[n][n]; // 读取棋盘 for (int i 0; i n; i) { String line sc.next(); for (int j 0; j n; j) { board[i][j] line.charAt(j); } } // 核心预处理所有连通分量 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 sc.nextInt() - 1; // 转为0-based int c sc.nextInt() - 1; System.out.println(result[r][c]); } } // BFS 寻找连通分量并填充结果 static void bfs(int startR, int startC) { Queueint[] queue new LinkedList(); Listint[] component new ArrayList(); // 记录当前分量包含的所有格子 queue.offer(new int[]{startR, startC}); visited[startR][startC] true; component.add(new int[]{startR, startC}); while (!queue.isEmpty()) { int[] cur queue.poll(); int r cur[0]; int c cur[1]; char currentColor board[r][c]; for (int d 0; d 4; d) { int nr r dx[d]; int nc c dy[d]; // 检查边界、未访问、颜色不同 if (nr 0 nr n nc 0 nc n !visited[nr][nc] board[nr][nc] ! currentColor) { visited[nr][nc] true; queue.offer(new int[]{nr, nc}); component.add(new int[]{nr, nc}); } } } // 将该连通分量的大小赋值给分量内的所有格子 int size component.size(); for (int[] cell : component) { result[cell[0]][cell[1]] size; } } }2. Go 语言实现Go 版本利用切片模拟队列内存控制更灵活执行效率极高非常适合处理大规模数据。package main import ( bufio fmt os ) var ( n, m int board [][]byte result [][]int visited [][]bool dx []int{0, 0, 1, -1} dy []int{1, -1, 0, 0} ) func main() { // 使用 bufio 提高读取效率 scanner : bufio.NewScanner(os.Stdin) if !scanner.Scan() { return } fmt.Sscanf(scanner.Text(), %d %d, n, m) board make([][]byte, n) result make([][]int, n) visited make([][]bool, n) for i : 0; i n; i { scanner.Scan() line : scanner.Text() board[i] []byte(line) result[i] make([]int, n) visited[i] make([]bool, n) } // 预处理所有连通分量 for i : 0; i n; i { for j : 0; j n; j { if !visited[i][j] { bfs(i, j) } } } // 处理查询 for k : 0; k m; k { if !scanner.Scan() { break } var r, c int fmt.Sscanf(scanner.Text(), %d %d, r, c) // 坐标转换 fmt.Println(result[r-1][c-1]) } } func bfs(startR, startC int) { // 使用切片模拟队列 queue : [][2]int{{startR, startC}} component : [][2]int{{startR, startC}} visited[startR][startC] true head : 0 for head len(queue) { r, c : queue[head][0], queue[head][1] head currentColor : board[r][c] for d : 0; d 4; d { nr, nc : rdx[d], cdy[d] // 核心判断边界 未访问 颜色不同 if nr 0 nr n nc 0 nc n !visited[nr][nc] board[nr][nc] ! currentColor { visited[nr][nc] true queue append(queue, [2]int{nr, nc}) component append(component, [2]int{nr, nc}) } } } // 填充结果 size : len(component) for _, cell : range component { result[cell[0]][cell[1]] size } }五、复杂度分析指标分析结论时间复杂度预处理阶段每个格子最多进队出队一次耗时 O(N2)O(N2) 查询阶段 MM 次操作每次 O(1)O(1) 。O(N2M)O(N2M)空间复杂度需要存储棋盘、访问标记数组、结果数组以及 BFS 队列/列表。O(N2)O(N2)在 N1000,M10000N1000,M10000 的数据规模下运算量约为 106106 级别远低于一般机考 108108 的每秒限制能够轻松 AC。总结本题是典型的“静态图多源查询”问题。关键点识别出“颜色交替”即为图的边并将多次查询转化为一次全图遍历。技巧在 BFS 过程中暂存连通分量内的所有节点遍历结束后统一赋值避免了重复计算。希望这篇题解能帮助你掌握这类问题如果觉得有用欢迎点赞、收藏、关注后续将带来更多od机考真题解析
