手撕数据结构队列,以实现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;
}
|
wechat
