本文共 2597 字，大约阅读时间需要 8 分钟。

如何使用BFS解决迷宫问题

在编程中，迷宫问题是一个经典的路径finding问题。对于这个问题，广度优先搜索（BFS）算法是最优的选择，因为它能够在较短的代码量下，高效地找到从起点到终点的最短路径。

左手走法与右手走法

在迷宫问题中，左手走法和右手走法的定义是非常重要的。左手走法通常指的是从起点出发，优先探索左边的方向，而右手走法则相反。值得注意的是，从起点到终点的右手走法步数与从终点到起点的左手走法步数是相同的。因此，只需要编写一套左手走法的代码即可满足需求。

BFS算法实现

以下是使用C语言实现BFS算法的代码示例：

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define MAX 45#define DIR 4int mp[MAX][MAX];bool flag = false;void dfs(int x, int y, int dir, int step) {    if (mp[x][y]) {        flag = true;        printf("%d ", step);    }    for (int i = 3; i <= 6; i++) {        if (mp[a = x + DIR[(i + dir) % 4][0]][b = y + DIR[(i + dir) % 4][1]] >= 0) {            dfs(a, b, (dir + i) % 4, step + 1);            if (flag) return;        }    }}struct Point {    int x, y, step;} p, q;void bfs(int x, int y) {    p.x = x;    p.y = y;    p.step = 1;    mp[x][y] = -1;    deque
      
        dq;    dq.push_back(p);    while (1) {        p = dq.front();        dq.pop_front();        for (int i = 0; i < 4; i++) {            q.step = p.step + 1;            q.x = p.x + DIR[i][0];            q.y = p.y + DIR[i][1];            if (mp[q.x][q.y] == 0) {                mp[p.x][q.y] = -1;                dq.push_back(q);            }            if (mp[q.x][q.y] > 0) {                dq.clear();                printf("%d", q.step);                return;            }        }    }}int main() {    int T;    scanf("%d", &T);    while (T--) {        memset(mp, -1, sizeof(mp));        int w, h;        scanf("%d %d", &w, &h);        for (int i = 1; i <= h; i++) {            scanf("%s", str + 1);            for (int k = 1; k <= w; k++) {                if (str[k] == '.') {                    mp[i][k] = 0;                } else if (str[k] == 'S') {                    stax = i;                    stay = k;                } else if (str[k] == 'E') {                    endx = i;                    endy = k;                }            }        }        flag = false;        mp[stax][stay] = 0;        mp[endx][endy] = 1;        dfs(stax, stay, 1, 1);        flag = false;        mp[stax][stay] = 1;        mp[endx][endy] = 0;        dfs(endx, endy, 1, 1);        mp[endx][endy] = 1;        bfs(stax, stay);        puts("");    }}
      
     
    
   

代码解释

实现思路

通过上述代码，我们可以高效地解决迷宫问题，找到从起点到终点的最短路径。

转载地址：http://dfxfk.baihongyu.com/