算法标签：

搜索 BFS 动态规划 贪心

题解：

这是一道通过广度优先搜索（BFS）算法来解决在给定地图中寻找从起点到终点最短路径（考虑路径段数）的问题，下面是详细的题解：

问题描述

给定一个大小为 r 行 c 列的地图，地图上存在障碍物（用 X 表示），要求从给定的起点 (x1, y1) 找到一条到终点 (x2, y2) 的最短路径。这里的最短路径不仅考虑路径长度，还需考虑路径的段数（当改变方向时路径段数增加），并且要输出从起点到终点最少经过的路径段数。如果无法到达终点，则输出 impossible。

解题思路

1. 数据结构与初始化：
   • 定义 Node 结构体来存储节点信息，包括节点的坐标 (x, y)、从起点到该节点的路径段数 steps 以及到达该节点的方向 dir。
   • 使用二维字符数组 g 来存储地图信息，二维布尔数组 vis 标记节点是否被访问过。
   • 初始化方向数组 dir 表示上下左右四个方向。
   • 从输入中读取地图的行数 r 和列数 c，并初始化相关变量。
2. 读取地图：
   • 逐行读取地图信息，将字符存入 g 数组中。
3. 广度优先搜索（BFS）：
   • 利用优先队列 q 来存储待访问的节点，优先队列按照路径段数 steps 从小到大排序（通过重载 operator< 实现）。
   • 从起点开始，将起点节点的信息（坐标、初始路径段数为 1、初始方向为 -1）存入优先队列。
   • 当优先队列不为空时，取出队首节点进行处理：
     • 标记该节点为已访问。
     • 检查是否到达终点，如果到达，记录路径段数并返回 true。
     • 遍历四个方向，计算新节点的坐标：
       • 判断新节点是否越界，若越界则跳过。
       • 如果新节点未被访问：
         • 根据当前节点的方向和新方向来确定新节点的路径段数（若方向改变，路径段数加 1；否则不变）。
         • 如果新节点是障碍物且不是终点，则跳过；否则将新节点加入优先队列。
   • 如果遍历完所有节点都未到达终点，则返回 false。
4. 结果输出：
   • 对于每一组起点和终点，调用 BFS 函数寻找路径。
   • 如果找到路径，输出路径的段数；如果未找到路径，输出 impossible。

关键步骤解释

1. 优先队列的使用：使用优先队列可以保证每次取出的节点都是当前路径段数最少的节点，从而优先探索可能的最短路径，提高搜索效率。
2. 路径段数的计算：在 BFS 过程中，根据节点的方向变化来准确计算路径段数。当新节点的方向与当前节点的方向不同时，路径段数增加 1。
3. 访问标记的作用：通过 vis 数组标记已访问的节点，避免重复访问，防止陷入死循环，同时保证每个节点只被访问一次，确保算法的正确性。

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <cmath>
using namespace std;

// 定义节点结构体，用于存储节点信息
struct Node {
    int x, y;
    int steps;
    int dir;
    // 重载小于运算符，用于优先队列排序
    bool operator<(const Node& t1) const {
        return this->steps > t1.steps;
    }
};

// 地图数组，存储地图信息
char g[80][80];
// 访问标记数组，记录节点是否被访问过
bool vis[80][80];
// 方向数组，用于表示上下左右四个方向
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// 记录从起点到终点的段数
int segments;
// 地图的行数和列数
int r, c;

// 广度优先搜索函数，用于寻找从起点到终点的最短路径
bool bfs(int x1, int y1, int x2, int y2) {
    // 优先队列，用于存储待访问的节点
    priority_queue<Node> q;
    Node newnode, topNode;
    newnode.x = x1;
    newnode.y = y1;
    newnode.dir = -1;
    newnode.steps = 1;
    q.push(newnode);

    while (!q.empty()) {
        topNode = q.top();
        q.pop();
        int ci, cj;
        vis[topNode.x][topNode.y] = true;

        // 如果到达终点，记录段数并返回 true
        if (topNode.x == x2 && topNode.y == y2) {
            segments = topNode.steps;
            return true;
        }

        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            ci = topNode.x + dir[i][0];
            cj = topNode.y + dir[i][1];
            newnode.x = ci;
            newnode.y = cj;

            // 判断新节点是否越界
            if (ci < 0 || ci > r + 1 || cj < 0 || cj > c + 1)
                continue;

            // 如果新节点未被访问过
            if (!vis[ci][cj]) {
                if (topNode.dir == -1) {
                    newnode.dir = i;
                } else if (topNode.dir != i) {
                    newnode.steps = topNode.steps + 1;
                } else {
                    newnode.steps = topNode.steps;
                }
                newnode.dir = i;

                // 如果新节点是障碍物，且不是终点，则跳过
                if (g[ci][cj] == 'X') {
                    if (ci == x2 && cj == y2)
                        q.push(newnode);
                    continue;
                }
                q.push(newnode);
            }
        }
    }
    return false;
}

int main() {
    int t = 0;
    int x1, x2, y1, y2, tt;
    while (cin >> c >> r && r) {
        string str;
        memset(g, 0, sizeof(g));
        getline(cin, str);

        // 读取地图信息
        for (int i = 1; i <= r; i++) {
            getline(cin, str);
            for (int j = 1; j <= c; j++) {
                g[i][j] = str[j - 1];
            }
        }

        cout << "Board #" << ++t << ":" << endl;
        tt = 0;
        while (true) {
            cin >> x1 >> y1 >> x2 >> y2;
            if (x1 == 0) break;
            memset(vis, 0, sizeof(vis));

            // 调用 bfs 函数寻找路径
            if (bfs(y1, x1, y2, x2)) {
                cout << "Pair " << ++tt << ": " << segments << " segments." << endl;
            } else {
                cout << "Pair " << ++tt << ": impossible." << endl;
            }
        }
        cout << endl;
    }
    return 0;
}

🧠 题解（Solution）

本题是一个最少折线段数路径搜索问题，可以通过**广度优先搜索（BFS）**结合状态记录来解决。

✅ 状态设计

每个位置状态不仅包括其坐标 $(x, y)$，还应包含：

当前移动方向（水平/垂直，4种方向）；

当前使用的线段数量（即拐弯次数 + 1）；

✅ 搜索逻辑

从起始点四个方向出发，每个方向初始段数设为 $1$；

对每一步，若方向不变，则段数不变；若换方向，段数加 $1$；

每次只能走到没有棋子的位置或终点；

路径最多允许 $3$ 次拐弯（即最多 $4$ 段）；

搜索结束后，找到所有可行路径中线段数最小的那个。

✅ 注意事项

路径可以离开棋盘再回来，所以可以在边界上继续往外走；

注意坐标系统是从 $1$ 开始，数组下标应减 $1$；

起点和终点在搜索前需要暂时设为空（' '），否则可能无法通行；

多个棋盘及多个坐标对，每组处理完需输出一个空行。

代码实现：

#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define max_n 1010
using namespace std;
int mapp[max_n][max_n];
int vis[max_n][max_n];
int X1, Y1, X2, Y2, n, m, cnt;
int mov[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

struct node {
    int x, y, z;
    int step;
    bool friend operator <(node a, node b) {
        return a.step > b.step;
    }
}now, Next;

void bfs(int X, int Y, int Z) {
    memset(vis, 0, sizeof(vis));
    bool flag = false;
    priority_queue<node> q;
    now.x = X;
    now.y = Y;
    now.z = Z;
    now.step = 0;
    q.push(now);
    while(!q.empty()) {
        Next = q.top();
        q.pop();
        if(Next.x == X2 && Next.y == Y2) {
            flag = true;
            break;
        }
        if(vis[Next.x][Next.y]) continue;
        vis[Next.x][Next.y] = 1;
        for(int i = 0; i < 4; i++) {
            now.x = Next.x + mov[i][0];
            now.y = Next.y + mov[i][1];
            if(now.x < 0 || now.x > n + 1 || now.y < 0 || now.y > m + 1 || mapp[now.x][now.y] || vis[now.x][now.y] == 1)
                continue;
            if(i != Next.z) {
                now.z = i;
                now.step = Next.step + 1;
                q.push(now);
            }
            else {
                now.z = i;
                now.step = Next.step;
                q.push(now);
            }
        }
    }
    if(flag) printf("Pair %d: %d segments.\n", cnt++, Next.step);
    else printf("Pair %d: impossible.\n", cnt++);
}

int main() {
    int p = 1;char ch;
    while(scanf("%d %d", &m, &n) && (n + m)) {
        memset(mapp, 0, sizeof(mapp)); //注意初始化 
        for(int i = 1; i <= n; i++) {
            getchar();
            for(int j = 1; j <= m; j++) {
                scanf("%c", &ch);
                if(ch == 'X') mapp[i][j] = 1;
                else mapp[i][j] = 0;
            }
        }
        cnt = 1;
        printf("Board #%d:\n", p++);
        while(scanf("%d %d %d %d", &Y1, &X1, &Y2, &X2) && (X1 + X2 + Y1 + Y2)) {
            int ant = mapp[X2][Y2];  
            mapp[X2][Y2] = 0;  //终点位置更改一下
            bfs(X1, Y1, -1);
            mapp[X2][Y2] = ant;
        }
        printf("\n");
    }
    return 0;
}