当前位置：首页 > 洛谷 > 洛谷4554题解：BFS算法优化最短路径求解（附代码详解）

洛谷4554题解：BFS算法优化最短路径求解（附代码详解）

3个月前 (06-05)

一、题目解读

洛谷4554题要求在一个n×m的网格中，计算从点(x1,y1)到点(x2,y2)的最短路径距离。路径上的每个格子包含字符，若相邻格子字符不同，则需要额外步数。题目核心在于处理字符差异对路径长度的影响，并高效求解最短路径。

二、解题思路

采用广度优先搜索（BFS）算法，结合双向队列（deque）优化。关键思路：

1. 初始化距离数组dist，标记所有点到起点距离为无穷；

2. 使用双向队列存储待遍历节点：若相邻节点与当前节点字符相同，则插入队首（无需额外步数，优先扩展）；若不同，则插入队尾（需额外步数）；

3. 通过四个方向遍历，动态更新最短距离，直至到达终点。

三、解题步骤

1. 数据预处理：将输入坐标转换为1-based索引（原代码中x1++,y1++,x2++,y2++实现）；

2. BFS执行：

起点入队，标记距离为0；

循环弹出队首节点，遍历四周：

判断边界和字符差异，计算移动成本（cost）；

若更新距离更优，则更新dist并调整入队位置（同字符入队首，异字符入队尾）；

3. 终止条件：遍历至终点(x2,y2)，返回其最短距离。

四、代码与注释

#include <iostream>
#include <deque>
#include <cstring>
using namespace std;

const int N = 510;  
char grid[N][N];  
int dist[N][N];  
int dx[] = {-1, 1, 0, 0};  // 方向偏移量  
int dy[] = {0, 0, -1, 1};
int n, m, x1, y1, x2, y2;

int bfs() {  
    // 初始化距离数组为无穷  
    memset(dist, 0x3f, sizeof dist);  
    deque<pair<int, int>> q;  
    q.push_back({x1, y1});  
    dist[x1][y1] = 0;  
    
    while (!q.empty()) {  
        auto t = q.front();  
        q.pop_front();  
        
        for (int i = 0; i < 4; i++) {  
            int nx = t.first + dx[i], ny = t.second + dy[i];  
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;  
            
            // 计算移动成本（字符不同需额外步数）  
            int cost = (grid[nx][ny]!= grid[t.first][t.second]);  
            if (dist[nx][ny] > dist[t.first][t.second] + cost) {  
                dist[nx][ny] = dist[t.first][t.second] + cost;  
                // 根据成本决定入队位置（优化关键）  
                if (cost == 0) q.push_front({nx, ny});  
                else q.push_back({nx, ny});  
            }  
        }  
    }  
    return dist[x2][y2];  
}

int main() {  
    while (cin >> n >> m, n || m) {  
        for (int i = 1; i <= n; i++)  
            for (int j = 1; j <= m; j++)  
                cin >> grid[i][j];  
        cin >> x1 >> y1 >> x2 >> y2;  
        x1++, y1++, x2++, y2++; // 转换为1-based索引  
        cout << bfs() << endl;  
    }  
    return 0;  
}

注释说明：

1.双向队列通过区分插入位置实现分层遍历，减少冗余计算；

2.字符差异判断（grid[nx][ny]!= grid[t.first][t.second]）直接影响路径成本；

3.坐标转换（索引+1）适配1-based题目要求。