当前位置：首页 > 洛谷 > 洛谷P1747题解：遍历最短路径（BFS算法优化）

洛谷P1747题解：遍历最短路径（BFS算法优化）

5个月前 (07-17)

一、题目解读

洛谷P1747题目要求模拟中国象棋中“马”的移动规则，计算从任意起点到终点所需的最小步数。题目中马的移动方式包括传统的“日”字步（8种方向）及特殊“田”字步（4种方向），需在限定范围内寻找最短路径。问题核心在于利用图论算法解决多方向移动的最短路径问题。

二、解题思路

采用**广度优先搜索（BFS）**算法，其核心思想是逐层遍历所有可能状态，直到找到目标点。由于马的移动具有多种方向，需预先定义12种偏移量（dx、dy数组），通过队列维护待扩展节点。每次从队列取出当前节点，尝试所有合法移动方向，标记已访问状态并更新步数，直至到达终点。该算法保证首次到达终点的路径即为最短路径。

三、解题步骤

1. 初始化：定义队列q，访问标记visited数组，将起点入队并标记访问。

2. BFS循环：

取出队头节点（当前位置及步数）。

遍历12种移动方向，计算新坐标（nx, ny）。

判断新坐标是否越界或已访问，若合法：

若为新终点，返回当前步数+1；

否则标记visited并加入队列，步数+1。

3. 终止条件：队列为空时，返回-1（理论上不会执行）。

四、代码与注释

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

const int MAXN = 50; // 棋盘最大范围
const int dx[] = {-2,-2,-1,-1,1,1,2,2,-2,2,-2,2};
const int dy[] = {-1,1,-2,2,-2,2,-1,1,-2,-2,2,2};

// 节点结构（坐标+步数）
struct Point {
    int x, y, steps;
};

// 核心BFS函数
int bfs(int startX, int startY) {
    if(startX == 1 && startY == 1) return 0; // 起点即终点直接返回0
    
    queue<Point> q;
    bool visited[MAXN][MAXN] = {false};
    q.push({startX, startY, 0}); // 起点入队
    visited[startX][startY] = true;
    
    while(!q.empty()) {
        Point current = q.front(); // 取出当前节点
        q.pop();
        
        for(int i = 0; i < 12; i++) { // 遍历12种移动方向
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];
            
            if(nx < 1 || ny < 1 || nx >= MAXN || ny >= MAXN) continue; // 越界判断
            if(visited[nx][ny]) continue; // 已访问跳过
            
            if(nx == 1 && ny == 1) { // 到达终点
                return current.steps + 1;
            }
            
            visited[nx][ny] = true; // 标记访问
            q.push({nx, ny, current.steps + 1}); // 新节点入队
        }
    }
    return -1; // 理论上不会执行到这里
}

int main() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2; // 输入两个起点坐标
    
    cout << bfs(x1, y1) << endl; // 输出两起点的最短路径
    cout << bfs(x2, y2) << endl;
    
    return 0;
}