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

一、题目解读

洛谷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题目要求。

五、总结

本解法通过BFS结合双向队列，巧妙利用字符状态优化搜索顺序，避免重复计算不同字符路径。核心在于根据移动成本动态调整入队策略，显著降低时间复杂度。掌握此类优化技巧对处理带条件约束的最短路径问题具有重要参考价值。