1 条题解
-
0
#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
- 上传者