题解 | #迷宫问题#

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;


map<int, vector<int>> bfs(vector<vector<int>> matrix, int n, int m)
{
    vector<int> dx = { 1, 0,-1,0 };
    vector<int> dy = { 0, 1,0,-1 };
    int result = 0;
    queue<vector<vector<int>>> q;
    map<int, vector<int>> length_set;
    q.push({ {0,0,0 },{} });
    while (!q.empty())
    {
        //q分为两行，一行记录目前的位置，和走过的长度，零一行记录走过的路程
        int x, y;
        x = q.front()[0][0];
        y = q.front()[0][1];
        int path_length = q.front()[0][2];

        vector<int> temp = q.front()[1];
        q.pop();
        temp.push_back(x);
        temp.push_back(y);

         if (x == n - 1 && y == m - 1)
        {

            length_set[path_length] = temp;
            temp = {};
        }
        else
        {
            for (int i = 0; i != 4; ++i)
            {
                int nx = dx[i] + x;
                int ny = dy[i] + y;
                if (nx >= 0 && nx < n && ny < m && ny >= 0)
                {
                    if (temp.size() >= 4)
                    {
                        if (ny != temp[temp.size() - 3] || nx != temp[temp.size() - 4])
                        {
                            if (matrix[nx][ny] == 0)
                            {
                                q.push({ { nx,ny,path_length + 1 },temp });

                            }
                        }
                    }
                    else
                    {
                        if (matrix[nx][ny] == 0)
                        {
                            q.push({ { nx,ny,path_length + 1 },temp });

                        }
                    }
                }
            }
        }

    }
    return length_set;
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m, 0));
    for (int i = 0; i != n; ++i) {
        for (int j = 0; j != m; ++j) {
            int k;
            cin >> k;
            matrix[i][j] = k;
        }
    }
    map<int, vector<int>> k = bfs(matrix, n, m);
    auto i = k.begin();
    for (int j = 0; j != i->second.size() / 2; ++j) {
        cout << "(" << i->second[2 * j] << "," << i->second[2 * j + 1] << ")" << endl;
    }

}
// 64 位输出请用 printf("%lld")

我也不知道是广度搜索还是深度搜索，反正是搜索，用queue这个，FIFO属性。