题解：P14326 [JOI2022 预选赛 R2] 地毯 / Carpet

Oberon_Qwl · 2025-10-28 20:18:52 · 题解

P14326 [JOI2022 预选赛 R2] 地毯 / Carpet 题解

题目大意

给定一个 H 行 W 列的网格，每个格子为白色 .或黑色 #。棋子从 (1,1) 出发，每次只能移动到颜色不同的上下左右相邻格子，求到达 (H,W) 的最小步数，无法到达则输出 −1。

思路

第一眼想到的就是 BFS,按递增顺序遍历所有格子，每个格子仅入队一次，首次到达终点时的步数即为最短路径，时间复杂度为 (O(H \times W))，满足 (H,W \leq 500) 的数据规模。

::::info[为什么不用 DFS?] 深搜可能会优先探索深层路径，没有保证首次到达终点时步数最小，得遍历所有路径后再对比，这样时间复杂度就很高。 ::::

首先，初始化。

再是对队列的处理：每次取出队首格子，遍历其四个相邻方向。注意检查相邻格子是否在网格范围内；相邻格子颜色是否与当前格子不同；相邻格子是否未被访问过（避免重复处理）。

然后更新状态，若满足所有条件，更新相邻格子的距离（当前距离 + 1），并将其加入队列。终止条件：队列空（无路径）或到达终点（返回距离）。

代码实现

变量定义。

#include<bits/stdc++.h>
using namespace std;

const int MAX = 505;  // 网格最大尺寸（适配 H,W ≤ 500）
char g[MAX][MAX];     // 存储网格颜色
int d[MAX][MAX];      // 存储起点到各格子的最短距离，-1 表示未访问
int dx[] = {-1, 1, 0, 0};  // 上下左右四个方向的 x 偏移
int dy[] = {0, 0, -1, 1};  // 上下左右四个方向的 y 偏移
int h, w;             // 输入的网格行数和列数

核心逻辑：

• 输入处理。

  cin >> h >> w;
  for (int i = 0; i < h; i++) {
  cin >> g[i];  // 读取每行网格数据（0-based 索引）
  }
  memset(d, -1, sizeof(d));  // 距离数组初始化为 -1（未访问）

• BFS 队列初始化。

  queue<pair<int, int> > q;  // 队列存储格子坐标 (x, y)
  d[0][0] = 0;  // 起点 (0,0) 距离为 0
  q.push(make_pair(0, 0));  // 起点入队

• 主循环。

  while (!q.empty()) {
  // 取出队首格子
  int x = q.front().first;
  int y = q.front().second;
  q.pop();
  
  // 遍历四个相邻方向
  for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];  // 相邻格子的 x 坐标
      int ny = y + dy[i];  // 相邻格子的 y 坐标
  
      // 1. 边界检查：确保相邻格子在网格内
      if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
          // 2. 颜色规则检查：相邻格子颜色与当前不同
          if (g[nx][ny] != g[x][y]) {
              // 3. 未访问检查：确保该格子未被处理过
              if (d[nx][ny] == -1) {
                  d[nx][ny] = d[x][y] + 1;  // 更新距离
                  q.push(make_pair(nx, ny));  // 新格子入队
              }
          }
      }
  }
  }

• 输出。

  cout << d[h-1][w-1] << endl;  // 输出终点 (h-1, w-1) 的距离

  ::::success[完整代码]

  
  #include <bits/stdc++.h>
  using namespace std;

const int MAX = 505; char g[MAX][MAX]; int d[MAX][MAX]; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; int h, w;

int main() { cin >> h >> w; for (int i = 0; i < h; i++) { cin >> g[i]; } memset(d, -1, sizeof(d)); queue<pair<int, int>> q; d[0][0] = 0; q.push(make_pair(0, 0));

while (!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
            if (g[nx][ny] != g[x][y] && d[nx][ny] == -1) {
                d[nx][ny] = d[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
}

cout << d[h-1][w-1] << endl;
return 0;

}

::::

---

完结散花。