启发式搜索——用“直觉”指导搜索方向

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>  // 用于 memset
using namespace std;

// 定义格子节点，包含坐标、已走代价g、启发式h
struct Node {
    int x, y;          // 坐标
    int g, h;          // g: 从起点到这里的实际步数, h: 启发值（曼哈顿距离）
    int f() const { return g + h; }  // 总代价 = 已走 + 估计剩余
    // 重载小于号，用于优先队列（我们希望小顶堆，所以用 > 比较）
    bool operator<(const Node& other) const {
        return f() > other.f();
    }
};

// 四个方向的偏移量：上下左右
int direction_x[] = {-1, 1, 0, 0};
int direction_y[] = {0, 0, -1, 1};

int main() {
    // 地图，0表示空地，1表示障碍，S是起点，E是终点
    vector<string> maze = {
        "001000",   // 第0行
        "0S0100",   // 第1行
        "001000",   // 第2行
        "000001",   // 第3行
        "0010E0",   // 第4行
        "000000"    // 第5行
    };
    int rows = 6, cols = 6;
    
    // 找到起点S和终点E的坐标
    int start_x, start_y, end_x, end_y;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (maze[i][j] == 'S') {
                start_x = i;
                start_y = j;
            }
            if (maze[i][j] == 'E') {
                end_x = i;
                end_y = j;
            }
        }
    }

    // 距离表：记录到达每个格子所需的最少步数（初始为极大值）
    vector<vector<int>> dist(rows, vector<int>(cols, 1e9));
    
    // 优先队列（小顶堆），存放待扩展的节点
    priority_queue<Node> pq;
    
    // 计算起点的启发值：曼哈顿距离到终点
    int init_h = abs(start_x - end_x) + abs(start_y - end_y);
    pq.push({start_x, start_y, 0, init_h});
    dist[start_x][start_y] = 0;   // 起点步数为0
    
    // 保存路径：用于最终输出（可选）
    // 这里为了简洁，只输出最短步数
    
    while (!pq.empty()) {
        Node cur = pq.top();   // 取出当前f值最小的节点
        pq.pop();
        
        // 如果已经到达终点，输出步数并结束
        if (cur.x == end_x && cur.y == end_y) {
            cout << "找到最短路径！所需步数 = " << cur.g << endl;
            return 0;
        }
        
        // 如果当前节点的g值已经比记录的最优值大，说明不是最优，跳过
        if (cur.g > dist[cur.x][cur.y]) continue;
        
        // 尝试向四个方向移动
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + direction_x[i];
            int ny = cur.y + direction_y[i];
            
            // 检查越界和障碍（障碍用'1'表示）
            if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue;
            if (maze[nx][ny] == '1') continue;
            
            int new_g = cur.g + 1;   // 新步数 = 当前步数 + 1
            if (new_g < dist[nx][ny]) {
                dist[nx][ny] = new_g;   // 更新最短步数
                int new_h = abs(nx - end_x) + abs(ny - end_y);  // 曼哈顿距离
                pq.push({nx, ny, new_g, new_h});
            }
        }
    }
    
    // 如果队列空了都没找到终点，说明无路可走
    cout << "没有路径能到达终点" << endl;
    return 0;
}

找到最短路径！所需步数 = 6