迷宫最短路径的一种解法

川长思鸟来 2022-12-13 12:43 108阅读 0赞

寻找迷宫出口的最短步数C++实现。

#include <iostream>
    #include <fstream>
    #include <cstring>
    #include <string>
    #include <queue>
    using namespace std;
    
    //标记全图状态，已经访问的按钮为1，未访问的为0
    int status[1000][1000];
    
    //标记每个小方格到出发点的距离
    int times[1000][1000];
    
    //队列
    queue<pair<int, int>> q;
    //全图
    string buff[1000];
    //H全图的高，W全图的宽
    int H, W;
    void f(int dx, int dy)
    { 
        if (dx > 0)
        { 
            if (status[dx - 1][dy] == 0 && buff[dx - 1][dy] != '1')
            { 
                status[dx - 1][dy] = 1;
                times[dx - 1][dy] = times[dx][dy] + 1;
                q.push(make_pair(dx - 1, dy));
            }
        }
        if (dx < H)
        { 
            if (status[dx + 1][dy] == 0 && buff[dx + 1][dy] != '1')
            { 
                status[dx + 1][dy] = 1;
                times[dx + 1][dy] = times[dx][dy] + 1;
                q.push(make_pair(dx + 1, dy));
            }
        }
        if (dy > 0)
        { 
            if (status[dx][dy - 1] == 0 && buff[dx][dy - 1] != '1')
            { 
                status[dx][dy - 1] = 1;
                times[dx][dy - 1] = times[dx][dy] + 1;
                q.push(make_pair(dx, dy - 1));
            }
        }
        if (dy < W)
        { 
            if (status[dx][dy + 1] == 0 && buff[dx][dy + 1] != '1')
            { 
                status[dx][dy + 1] = 1;
                times[dx][dy + 1] = times[dx][dy] + 1;
                q.push(make_pair(dx, dy + 1));
            }
        }
    }
    
    int main(int argc, char const *argv[])
    { 
        ifstream in;
        in.open("./migong.txt", ios::in);
        //文本中的地图总行数
        int line = 0;
        while (getline(in, buff[line++]))
            ;
        in.close();
        //获取数据总行数（图上下长度），W获取全图左右宽度
        H = line, W = buff[0].length();
        //初始化初始点
        q.push(make_pair(0, 0));
        //初始点状态为已访问
        status[0][0] = 1;
    
        //当前点的行数（dx），当前点的列数（dy）
        int dx = 0, dy = 0;
        while (true)
        { 
            //如果队列为空，说明已经查找完成
            if (q.size() == 0)
            { 
                break;
            }
            //遍历队列
            dx = q.front().first;
            dy = q.front().second;
            q.pop();
            f(dx, dy);
        }
        for (int i = 0; i < H; i++)
        { 
            for (int j = 0; j < W; j++)
            { 
                cout << times[i][j] << " ";
            }
            cout << endl;
        }
    
        return 0;
    }