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

_JeanW_

534人浏览 · 2026-03-17 22:59:46

_JeanW_ · 2026-03-17 22:59:46 发布

一、题目描述📝

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

只能从黑色格走到相邻的白色格

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

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

输入描述

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

输出描述
        m行，每行一个数表示每个询问的答案。

补充说明

        对于全部的测试点，保证1≤n≤1000，1≤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) 。
根据数据范围， N=1000,M=10000 ，最坏情况下运算量约为 10^10 ，这会导致超时（TLE）。

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

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

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

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

三、算法步骤🛠️

读取输入：解析 N,MN,M 和棋盘矩阵。注意字符 '0' 和 '1' 的处理。
初始化：
- visited[N][N]：标记格子是否已被访问。
- result[N][N]：存储每个格子所属连通分量的大小。
遍历预处理：
- 双重循环遍历每个格子 (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) {
        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
	}
}

五、复杂度分析📊

指标	分析	结论
时间复杂度	预处理阶段每个格子最多进队出队一次，耗时 O(N2) ；查询阶段 MM 次操作，每次 O(1) 。	O(N2+M)
空间复杂度	需要存储棋盘、访问标记数组、结果数组，以及 BFS 队列/列表。	O(N2)