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

· · 题解

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

题目传送门

这道题的核心是在有 “颜色交替” 限制的网格中寻找最短路径，由于每次移动的代价相同（步数 + 1），广度优先搜索（BFS） 是最优解法，能确保首次到达终点时的步数就是最小值~~~

#include <bits/stdc++.h>
using namespace std;
// 变量定义（沿用题目习惯的1-based索引）
int h, w;                  // 网格行数、列数
char c[505][505];          // 存储网格颜色（c[x][y]表示第x行第y列的颜色）
int t[505][505];           // 距离数组：t[x][y]是到达(x,y)的最小步数
int dx[4] = {1, -1, 0, 0}; // 方向数组：下、上、右、左（x坐标偏移）
int dy[4] = {0, 0, 1, -1}; // 方向数组：下、上、右、左（y坐标偏移）
struct node {
    int x, y, step;
};// 存储格子状态的结构体（坐标x、y，当前步数step）
queue<node> p; // BFS队列
int main() {
    // 1. 输入与初始化
    cin >> h >> w;
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            cin >> c[i][j];
            t[i][j] = 1e6; // 初始化为极大值，代表未访问
        }
    }
    // 起点入队：(1,1)，初始步数0
    p.push({1, 1, 0});
    t[1][1] = 0;
    // 2. BFS遍历
    while (!p.empty()) {
        node net = p.front(); // 取出队首状态
        p.pop();
        // 到达终点，直接输出结果（BFS首次到达即最短）
        if (net.x == h && net.y == w) {
            cout << net.step;
            return 0;
        }
        // 剪枝：当前步数不是该格子的最短路径，跳过
        if (net.step > t[net.x][net.y]) {
            continue;
        }
        // 遍历四个方向
        for (int i = 0; i < 4; ++i) {
            int xx = net.x + dx[i]; // 相邻格子的x坐标
            int yy = net.y + dy[i]; // 相邻格子的y坐标

            // 检查边界合法性：xx在[1,h]，yy在[1,w]
            if (xx < 1 || xx > h || yy < 1 || yy > w) {
                continue;
            }
            // 检查颜色合法性：相邻格子与当前格子颜色不同
            if (c[xx][yy] == c[net.x][net.y]) {
                continue;
            }
            // 计算新步数，检查路径是否更优
            int new_step = net.step + 1;
            if (new_step < t[xx][yy]) {
                t[xx][yy] = new_step; // 更新最短步数
                p.push({xx, yy, new_step}); // 加入队列
            }
        }
    }
    // 3. 无法到达终点
    cout << -1;
    return 0;
}

时间复杂度

O(H×W)

彩蛋代码

#include <bits/stdc++.h>
using namespace std;
int h,w,ans,t[505][505],dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};
char c[505][505];
struct node{
    int x,y,step;
};
queue<node>p;
int main() {
    cin>>h>>w;
    for(int i=1;i<=h;++i){
        for(int j=1;j<=w;++j){
            cin>>c[i][j];
        t[i][j]=1e6;
        }
    }
    p.push({1,1,0});
    t[1][1]=0;
    while(!p.empty()){
        node net=p.front();
        p.pop();
        if(net.x==h&&net.y==w){
            cout<<net.step;
            return 0;
        }
        for(int i=1;i<=4;++i){
            int xx=net.x+dx[i],yy=net.y+dy[i];
            if(xx<1||yy<1||xx>h||yy>w||c[xx][yy]==c[net.x][net.y]||t[xx][yy]<net.step){
                continue;
            }
            t[xx][yy]=net.step+1;
            p.push({xx,yy,net.step+1});
        }
    }
    cout<<-1;

    return 0;
}

逃~~~