1 条题解

  • 0
    @ 2026-2-17 22:24:37
    #include<bits/stdc++.h>
    using namespace std;
    
    // 棋盘最大尺寸,适配题目n,m≤500的要求
    const int MAXN = 505;
    // 无穷大常量,用于初始化距离数组
    const int INF = 0x3f3f3f3f;
    // 四个移动方向:上、下、左、右
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    
    char mp[MAXN][MAXN];  // 存储棋盘的格子类型
    int dist[MAXN][MAXN];  // 存储起点到每个格子的最小花费
    
    int main()
    {
        // 关闭cin同步,加速输入输出,应对多组数据
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int n, m;
        // 多组数据循环,当n和m均为0时结束输入
        while(cin >> n >> m && (n || m))
        {
            // [1] 读取n*m的棋盘,使用1-based坐标,和题目输入对应
            for(int i = 1; i <= n; i++)
            {
                cin >> mp[i] + 1; // mp[i]+1 表示从第1列开始存储,适配1-based索引
            }
    
            // [2] 读取起点(x1,y1)和终点(x2,y2)
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
    
            // [3] 初始化距离数组为无穷大,起点的花费为0
            memset(dist, 0x3f, sizeof(dist));
            dist[x1][y1] = 0;
    
            // [4] 0-1 BFS的双端队列,存储格式:{当前花费, {x坐标, y坐标}}
            deque<pair<int, pair<int, int>>> dq;
            dq.push_back({0, {x1, y1}}); // 起点入队
    
            // [5] 0-1 BFS核心循环
            while(!dq.empty())
            {
                // 取出队首的当前状态
                auto cur = dq.front();
                dq.pop_front();
                int cur_cost = cur.first;
                int x = cur.second.first;
                int y = cur.second.second;
    
                // 剪枝:如果当前状态的花费已经大于已知的最小花费,直接跳过
                if(cur_cost > dist[x][y]) continue;
    
                // 遍历四个移动方向
                for(int i = 0; i < 4; i++)
                {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    // 合法性校验:坐标必须在棋盘范围内
                    if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
    
                    // 计算移动花费:格子类型相同花费0,不同花费1
                    int cost = (mp[nx][ny] == mp[x][y]) ? 0 : 1;
    
                    // 如果新路径的花费更小,更新距离并加入队列
                    if(dist[nx][ny] > dist[x][y] + cost)
                    {
                        dist[nx][ny] = dist[x][y] + cost;
                        // 0花费加入队首,1花费加入队尾,保证队列的单调性
                        if(cost == 0)
                        {
                            dq.push_front({dist[nx][ny], {nx, ny}});
                        }
                        else
                        {
                            dq.push_back({dist[nx][ny], {nx, ny}});
                        }
                    }
                }
            }
    
            // [6] 输出起点到终点的最小花费
            cout << dist[x2][y2] << '\n';
        }
    
        return 0;
    }
    
    • 1

    信息

    ID
    1302
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    1
    已通过
    1
    上传者