题解 | #迷宫问题#

#include<iostream>
#include<vector>
using namespace std;
//结点创建类
typedef struct node {
    int x, y, len;
    node* father, *left, *right, *up, *down;
    node(int x0 = 0, int y0 = 0, int l0 = 0, node* f = nullptr, node* l = nullptr,
         node* r = nullptr, node* u = nullptr, node* d = nullptr): x(x0), y(y0), len(l0),
        father(f), left(l), right(r), up(u), down(d) {}
}* tree;
node* create(int** map, int n, int m) {
    tree t = new node;
    vector<node*> q;
    q.push_back(t);
    int i = 0;
    while (q[i]->x != n - 1 || q[i]->y != m - 1) { //当没达到最后一个结点
        //先判断右边是否可走，条件如下3条
        //q[i]->y+1!=m右边未到边界
        //!q[i]->father没父亲即起点  或者 q[i]->father->y!=q[i]->y+1右边不是本格父亲
        //map[q[i]->x][q[i]->y+1]    可走
        if (q[i]->y + 1 != m && (!q[i]->father || q[i]->father->y != q[i]->y + 1) &&
                !map[q[i]->x][q[i]->y + 1]) {
            q[i]->right = new node(q[i]->x, q[i]->y + 1, q[i]->len + 1,
                                   q[i]); //本格右边路径添加
            q.push_back(q[i]->right);    //记录结点，右边新结点压入容器
        }
        if (q[i]->x + 1 != n && (!q[i]->father || q[i]->father->x != q[i]->x + 1) &&
                !map[q[i]->x + 1][q[i]->y]) {
            q[i]->down = new node(q[i]->x + 1, q[i]->y, q[i]->len + 1, q[i]);
            q.push_back(q[i]->down);
        }
        if (q[i]->y && (!q[i]->father || q[i]->father->y != q[i]->y - 1) &&
                !map[q[i]->x][q[i]->y - 1]) {
            q[i]->left = new node(q[i]->x, q[i]->y - 1, q[i]->len + 1, q[i]);
            q.push_back(q[i]->left);
        }
        if (q[i]->x && (!q[i]->father || q[i]->father->x != q[i]->x - 1) &&
                !map[q[i]->x - 1][q[i]->y]) {
            q[i]->up = new node(q[i]->x - 1, q[i]->y, q[i]->len + 1, q[i]);
            q.push_back(q[i]->up);
        }
        i++;
    }
    return q[i];
}
void print(node* t) {
    int n = t->len;
    int* x = new int[n];
    int* y = new int[n];
    for (int i = n - 1; i >= 0; i--, t = t->father) {
        x[i] = t->x;
        y[i] = t->y;
    }
    cout << "(0,0)" << endl;
    for (int i = 0; i < n; i++) {
        cout << "(" << x[i] << "," << y[i] << ")" << endl;
    }
}
int main() {
    int n, m, d;
    int** map = new int* [n];
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        map[i] = new int[n];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    node* end = create(map, n, m);
    print(end);
}