题解：学而思编程奇妙的棋盘

2026/8/17 9:56:11 拓冰建站浏览量

【题目来源】

学而思编程：奇妙的棋盘

【题目描述】

小猴在玩一个神奇的游戏，游戏中给出了一个 \(n×m\) 的棋盘，棋盘中的格子有的黑，有的白。我们每次可以选择任意一个格子进行操作，然后这个格子和所有与它颜色相同的相邻的同色连通块中的所有格子的颜色全部取反。

小猴想知道至少需要多少次操作可以使所有格子变成白色。

【输入】

第 \(1\) 行，\(2\) 个整数 \(n,m\)，表示棋盘尺寸。

接下来 \(n\) 行，每行一个字符串描述每一行的棋盘情况，其中'W'表示白色，'B'表示黑色。

【输出】

输出一个整数表示最少的操作次数。

【输入样例】

3 4
WBWB
BWBB
WBWW

【输出样例】

【核心思想】

问题分析：给定 \(n \times m\) 的黑白棋盘，每次操作选择一个格子，该格子及其同色连通块全部颜色取反。求使所有格子变白的最少操作次数。本质上是多源 01-BFS + 最优化枚举问题：将问题转化为从某起点出发，跨越颜色边界的次数（即连通块切换次数），枚举所有可能的第一次操作位置取最小值。
算法选择：
- 01-BFS：同色相邻边权为 \(0\)（同一连通块内无需额外操作），异色相邻边权为 \(1\)（跨越连通块需要一次操作）
- 全源枚举：枚举每个格子作为第一次操作的起点，取所有结果的最小值
关键步骤：
- 读取数据：读入 \(n, m\) 和棋盘 \(g[1..n][1..m]\)
- 枚举起点（\(stx = 1\) 到 \(n\)，\(sty = 1\) 到 \(m\)）：
  - 初始化 \(dis\) 为 \(\infty\)，双端队列加入 \((stx, sty)\)，\(dis[stx][sty] = 0\)
  - 01-BFS：
    - 取出队首 \((x, y)\)
    - 更新 \(res = \max(res, dis[x][y] + [g[x][y] = 'B'])\)（到达该点的切换次数 + 若该点为黑需最后翻转一次）
    - 遍历四个方向 \((nx, ny)\)：
      - 边权 \(op = [g[x][y] \neq g[nx][ny]]\)（\(0\) 或 \(1\)）
      - 若 \(dis[nx][ny] > dis[x][y] + op\)，更新并 push_front（\(op=0\)）或 push_back（\(op=1\)）
  - \(ans = \min(ans, res)\)
- 输出 \(ans\)
时间/空间复杂度：
- 时间复杂度：\(O(n^2 \cdot m^2)\)，枚举 \(n \cdot m\) 个起点，每次 01-BFS \(O(n \cdot m)\)
- 空间复杂度：\(O(n \cdot m)\)，距离数组和双端队列
多源 01-BFS 的核心思想：
- 连通块操作的性质：一次操作翻转整个同色连通块，因此同一连通块内的格子可视为"同一层"，跨越不同连通块才需要新的操作
- 距离的定义：\(dis[x][y]\) 表示从起点到 \((x,y)\) 所需跨越的颜色边界次数，即操作次数的"层数"
- 最后翻转的处理：\(res\) 取 \(\max(dis[x][y] + [g[x][y]='B'])\)，因为若终点为黑色，需要最后一次操作将其翻白
- 全源枚举的必要性：最优第一次操作位置不固定，需尝试所有可能起点
- 适用于连通块翻转、颜色变换、多源最优化类问题

【算法标签】

01BFS

【代码详解】

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII; // 定义坐标对类型
const int N = 75; // 最大棋盘尺寸
int n, m, ans=1e9; // n:行数, m:列数, ans:最少操作次数
char g[N][N]; // g[i][j]:棋盘第i行第j列的颜色（'W'白色/'B'黑色）
int dis[N][N]; // dis[i][j]:从起点到(i,j)的最少"颜色变化次数"
int dx[4] = {-1, 1, 0, 0}; // 四个方向的行偏移（上、下、左、右）
int dy[4] = {0, 0, -1, 1}; // 四个方向的列偏移// 0-1BFS：从(stx,sty)出发，计算使所有格子变白的最少操作次数
// 核心思想：同色连通块内操作一次全部翻转，所以跨越颜色边界才需要额外操作
int bfs(int stx, int sty)
{// 初始化距离为无穷大memset(dis, 0x3f, sizeof(dis));deque<PII> q; // 双端队列q.push_back({stx, sty});dis[stx][sty] = 0;int res = 0; // 记录从该起点出发的最大"层数"while (!q.empty()){auto [x, y] = q.front(); // 取出队首坐标q.pop_front();// 更新答案：当前点的距离 + 该点是否为黑色（如果是黑色需要额外一次操作）// 实际上res记录的是从起点出发，到达每个点所需的最少颜色切换次数的最大值// 加上该点自身颜色是否为黑（需要最后翻转一次）res = max(res, dis[x][y] + (g[x][y]=='B'));// 遍历四个相邻方向for (int i=0; i<4; i++){int nx = x + dx[i], ny = y + dy[i]; // 新坐标// 边界检查if (nx<1 || nx>n || ny<1 || ny>m) continue;// 计算边权：颜色相同则代价为0（在同个连通块内），不同则代价为1（需要跨连通块）int op = g[x][y] != g[nx][ny];// 松弛操作if (dis[nx][ny]> dis[x][y] + op){dis[nx][ny] = dis[x][y] + op;// 0-1BFS：同色（代价0）放队首，异色（代价1）放队尾if (op==0)q.push_front({nx, ny});elseq.push_back({nx, ny});}}}return res; // 返回从该起点出发使全棋盘变白的最少操作次数
}int main()
{cin >> n >> m; // 读入棋盘尺寸for (int i=1; i<=n; i++)for (int j=1; j<=m; j++)cin >> g[i][j]; // 读入棋盘// 枚举每个格子作为第一次操作的起点for (int i=1; i<=n; i++)for (int j=1; j<=m; j++){ans = min(ans, bfs(i,j)); // 取所有起点中的最小值}cout << ans << endl; // 输出最少操作次数return 0;
}

【运行结果】

3 4
WBWB
BWBB
WBWW
2

建站实战干货

题解：学而思编程 奇妙的棋盘

01BFS

题解：学而思编程奇妙的棋盘