【华为OD机试真题】黑白棋 · N×N棋盘移动范围问题（Java/Go）

一、题目描述📝

有一个 N×NN×N 的棋盘，由黑格子（用1表示）和白格子（用0表示）组成。
棋子在棋盘上可以上下左右移动，但必须遵循以下规则：

• 只能从黑色格走到相邻的白色格
• 或者从白色格走到相邻的黑色格
  （即：相邻的两个格子颜色必须不同才能移动）

任务：对于给定的棋盘和 MM 个查询，每个查询给出一个起始坐标 (i,j)(i,j) ，请计算从该格子开始能移动到的所有格子总数（包含起始格本身）。

输入描述

第一行两个正整数，表示n，m。下面n行，每行n个字符，字符是1或0分别表示黑格子和白格子，字符之间无空格。接下来m行，每行两个数i，j，用空格隔开，表示棋盘的第行第列的格子，需要计算该棋子从该格子的移动范围是多少格。

输出描述
m行，每行一个数表示每个询问的答案。补充说明对于全部的测试点，保证1≤n≤1000，1≤m≤10000。

数据范围

• 1≤n≤10001≤n≤1000
• 1≤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) 。
• 根据数据范围， N=1000,M=10000N=1000,M=10000 ，最坏情况下运算量约为 10101010 ，这会导致超时（TLE）。

3. 优化策略：预处理连通分量

由于棋盘是静态的，连通分量的结构不会改变。我们可以采用空间换时间的策略：

1. 预处理阶段：遍历整个棋盘，对每个未访问过的格子启动一次 BFS/DFS。
   • 找出该格子所属的整个连通分量。
   • 统计该分量的大小 SS 。
   • 将该分量内所有格子的答案都标记为 SS 。
2. 查询阶段：对于每个查询 (i,j)(i,j) ，直接 O(1)O(1) 返回预处理好的结果。

总时间复杂度： O(N2)O(N2) (预处理) + O(M)O(M) (查询) =O(N2+M)O(N2+M)，完全满足时限要求。

三、算法步骤🛠️

1. 读取输入：解析 N,MN,M 和棋盘矩阵。注意字符'0'和'1'的处理。
2. 初始化：
   • visited[N][N]：标记格子是否已被访问。
   • result[N][N]：存储每个格子所属连通分量的大小。
3. 遍历预处理：
   • 双重循环遍历每个格子 (i,j)(i,j) 。
   • 如果!visited[i][j]，启动 BFS：
     • 使用队列进行广度优先搜索。
     • 收集当前连通分量中的所有坐标。
     • 搜索条件：相邻且在边界内、未访问、颜色与当前格子不同。
     • 搜索结束后，将收集到的所有坐标在result数组中赋值为本次搜索的节点总数。
4. 处理查询：
   • 读取 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) { Queue<int[]> queue = new LinkedList<>(); List<int[]> 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 := r+dx[d], c+dy[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 } }

五、复杂度分析📊

在 N=1000,M=10000N=1000,M=10000 的数据规模下，运算量约为 106106 级别，远低于一般机考 108108 的每秒限制，能够轻松 AC。

总结🚀

本题是典型的“静态图多源查询”问题。

• 关键点：识别出“颜色交替”即为图的边，并将多次查询转化为一次全图遍历。
• 技巧：在 BFS 过程中暂存连通分量内的所有节点，遍历结束后统一赋值，避免了重复计算。

希望这篇题解能帮助你掌握这类问题！如果觉得有用，欢迎点赞、收藏、关注，后续将带来更多od机考真题解析！