题解 | #迷宫问题#
迷宫问题
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
时隔一个月我也震惊当初自己怎么写出这玩意
#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); }