华为机试_迷宫问题_启发式搜索(A*算法)

启发式搜索， 启发信息为当前位置到终点的曼哈顿距离，具体步骤看代码注释：

#include<bits/stdc++.h>
using namespace std;
int n, m;
queue<pair<int, int> > track;
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int maze[12][12];

/**
 * 当前点和终点的曼哈顿距离，作为每一步的选择依据
 */
int mhd(int x, int y) {
    return (n - 1 - x) + (m - 1 - y);
}

/**
 * 越界撞墙判断
 */
bool isvail(int x, int y) {
    return !(x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == 1);
}

void search(int x, int y) {
    // 到终点后输出轨迹
    if (x == n - 1 && y == m - 1) {
        while (!track.empty()) {
            pair<int, int> c = track.front();
            track.pop();
            printf("(%d,%d)\n", c.first, c.second);
        }
        return;
    }

    // 遍历四个方向，选择距离最近的做为下一步
    maze[x][y] = 1;
    int next_x, next_y;
    int best_mhd = 999;
    for (int i = 0; i < 4; ++i) {
        int ntx = x + dir[i][0];
        int nty = y + dir[i][1];
        if (isvail(ntx, nty)) {
            // 标记访问过的可行方向，之后不再访问
            maze[ntx][nty] = 1;
            if (mhd(ntx, nty) < best_mhd) {
                best_mhd = mhd(ntx, nty);
                next_x = ntx;
                next_y = nty;
            }
        }
    }
    track.push(pair<int, int>(next_x, next_y));
    search(next_x, next_y);
}


int main() {
    while (cin >> n >> m) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                scanf("%d", &maze[i][j]);
            }
        }
        track.push(pair<int, int>(0, 0));
        search(0, 0);

    }
}