专栏文章

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

OOberon_Qwl
P14326题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mingyuja
此快照首次捕获于
2025/12/02 02:15
3 个月前
此快照最后确认于
2025/12/02 02:15
3 个月前
查看原文

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

题目大意

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

思路

第一眼想到的就是 BFS,按递增顺序遍历所有格子，每个格子仅入队一次，首次到达终点时的步数即为最短路径，时间复杂度为 (O(H×W))(O(H \times W))，满足 (H,W≤500)(H,W \leq 500) 的数据规模。
为什么不用 DFS?
深搜可能会优先探索深层路径，没有保证首次到达终点时步数最小，得遍历所有路径后再对比，这样时间复杂度就很高。
首先，初始化。
再是对队列的处理：每次取出队首格子，遍历其四个相邻方向。注意检查相邻格子是否在网格范围内；相邻格子颜色是否与当前格子不同；相邻格子是否未被访问过（避免重复处理）。
然后更新状态，若满足所有条件，更新相邻格子的距离（当前距离 +1+ 1），并将其加入队列。终止条件：队列空（无路径）或到达终点（返回距离）。

代码实现

变量定义。
CPP
#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;             // 输入的网格行数和列数
核心逻辑：
  • 输入处理。
CPP
cin >> h >> w;
for (int i = 0; i < h; i++) {
    cin >> g[i];  // 读取每行网格数据（0-based 索引）
}
memset(d, -1, sizeof(d));  // 距离数组初始化为 -1（未访问）
  • BFS 队列初始化。
CPP
queue<pair<int, int> > q;  // 队列存储格子坐标 (x, y)
d[0][0] = 0;  // 起点 (0,0) 距离为 0
q.push(make_pair(0, 0));  // 起点入队
  • 主循环。
CPP
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));  // 新格子入队
                }
            }
        }
    }
}
  • 输出。
CPP
cout << d[h-1][w-1] << endl;  // 输出终点 (h-1, w-1) 的距离
完整代码CPP
#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;
}
完结散花。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...