手撕数据结构队列,以实现BFS算法,不使用原有的queue
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
| #include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std;
#define max_size 10
int px[4] = { 0, 0, -1, 1 }; int py[4] = { 1, -1, 0, 0 };
struct postion { int x, y; int ans = 0; }; struct path { int x, y; }; path pre[max_size][max_size]; struct map { int m, n; int app[max_size][max_size]; bool visited[max_size][max_size] = { false }; int x1, y1; int x2, y2; }; struct node { postion data; struct node* next; }; class queue { private: node* root; public: queue() { root = new node; root->next = NULL; } void push(postion data) { node* node1 = root; while (node1->next) { node1 = node1->next; } node* node2 = new node; node2->data = data; node2->next = nullptr; node1->next = node2; } postion front() { if (root->next == NULL) { return { -1,-1 }; } else { postion number = root->next->data; return number; } }; bool empty() { return root->next == NULL; } void pop() { if (root->next == NULL) return; node* node1 = root->next; root->next = node1->next; free(node1); } void printnode() { node* node1 = root->next; printf("队列:"); while (node1) { printf("-->(%d,%d)", node1->data.x, node1->data.y); node1 = node1->next; } printf("\n"); } ~queue() { while (root) { node* temp = root; root = root->next; delete temp; } } }; void bfs(map& site) { postion currentsite; postion nextsite; currentsite.x = site.x1; currentsite.y = site.y1; currentsite.ans = 0; site.visited[currentsite.x][currentsite.y] = true; queue app; app.push(currentsite); while (!app.empty()) { currentsite = app.front(); app.pop(); if (currentsite.x == site.x2 && currentsite.y == site.y2) { cout << "走出了迷宫!" << endl; cout << "共走了: " << currentsite.ans << " 步" << endl; path truepath[max_size* max_size]; cout << "走过的路径为:"; truepath[0].x = site.x2; truepath[0].y = site.y2; int number = 1; bool istrue = true; truepath[number] = pre[site.x2][site.y2]; while (istrue) { if (truepath[number].x == site.x1 && truepath[number].y == site.y1) { istrue = false; break; } else { number++; truepath[number] = pre[truepath[number - 1].x][truepath[number - 1].y]; } } cout << "这个的走过的路径为:"; for (int i = currentsite.ans;i >= 0;i--) { cout << "(" << truepath[i].x << "," << truepath[i].y << ")" << "-->"; } cout << "endl" << endl; return; } for (int i = 0; i < 4; i++) { nextsite.x = currentsite.x + px[i]; nextsite.y = currentsite.y + py[i]; if (nextsite.x >= 1 && nextsite.y >= 1 && !site.visited[nextsite.x][nextsite.y] && site.app[nextsite.x][nextsite.y] && nextsite.x <= site.m && nextsite.y <= site.n) { pre[nextsite.x][nextsite.y].x = currentsite.x; pre[nextsite.x][nextsite.y].y = currentsite.y; nextsite.ans = currentsite.ans + 1; site.visited[nextsite.x][nextsite.y] = true; app.push(nextsite); } } } cout << "没有走出迷宫" << endl; } int main() { cout << "请输入这个迷宫的长和宽 m 与 n:" << endl; map total; scanf_s("%d", &total.m); scanf_s("%d", &total.n); cout << "请输入这个迷宫的值,1代表可以通过的,0代表不可以通过的:" << endl; for (int i = 1; i <= total.m; i++) { for (int j = 1; j <= total.n; j++) { scanf_s("%d", &total.app[i][j]); } } cout << "请输入起点的值 (x1, y1): "; cin >> total.x1 >> total.y1; cout << "请输入终点的值 (x2, y2): "; cin >> total.x2 >> total.y2; if (total.x1 < 1 || total.x1 > total.m || total.y1 < 1 || total.y1 > total.n || total.app[total.x1][total.y1] == 0) { cout << "起点不合法!" << endl; return 0; } if (total.x2 < 1 || total.x2 > total.m || total.y2 < 1 || total.y2 > total.n || total.app[total.x2][total.y2] == 0) { cout << "终点不合法!" << endl; return 0; } bfs(total); return 0; }
|