1 #include<iostream> 2 using namespace std; 3 void bfs(int i1, int j1, int i2, int j2); 4 void deep(int i1, int j1,int i2,int j2); 5 bool dfs(int i, int j, int i2, int j2); 6 int dfs_f[10][10] = { 0 }; 7 int g[10][10] = { 8 {1,1,1,1,1,1,1,1,1,1}, 9 {1,0,0,1,0,0,0,1,0,1}, 10 {1,0,0,1,0,0,0,1,0,1}, 11 {1,0,0,0,0,1,1,0,0,1}, 12 {1,0,1,1,1,0,0,0,0,1}, 13 {1,0,0,0,1,0,0,0,0,1}, 14 {1,0,1,0,0,0,1,0,0,1}, 15 {1,0,1,1,1,0,1,1,0,1}, 16 {1,1,0,0,0,0,0,0,0,1}, 17 {1,1,1,1,1,1,1,1,1,1} }; 18 struct node 19 { 20 int i, j; 21 int pre; 22 }; 23 struct que 24 { 25 struct node s[100]; 26 int r, f; 27 }; 28 struct Stack 29 { 30 int s[100]; 31 int top; 32 }; 33 struct dfs_stack 34 { 35 struct node s[100]; 36 int top; 37 }dfs_s; 38 int main() 39 { 40 cout << "迷宫图:" << endl; 41 for (int i = 0; i < 10; i++) 42 { 43 for (int j = 0; j < 10; j++) 44 { 45 cout << g[i][j] << ' '; 46 } 47 cout << endl; 48 } 49 50 while (1) 51 { 52 int s_i, s_j, e_i, e_j; 53 cout << "起点i:"; 54 cin >> s_i; 55 cout << "起点j:"; 56 cin >> s_j; 57 cout << "终点i:"; 58 cin >> e_i; 59 cout << "终点j:"; 60 cin >> e_j; 61 62 cout << "BFS: "; 63 bfs(s_i,s_j,e_i,e_j); 64 cout << endl; 65 cout << "DFS: "; 66 deep(s_i, s_j, e_i, e_j); 67 cout << endl << endl; 68 69 } 70 return 0; 71 } 72 bool dfs(int i, int j, int i2,int j2) 73 { 74 75 if (i == i2 && j == j2) 76 { 77 struct node* p = new struct node; 78 p->i = i; 79 p->j = j; 80 dfs_s.s[++dfs_s.top] = *p; 81 delete p; 82 return true; 83 } 84 if (dfs_f[i + 1][j] == 0 && g[i + 1][j] == 0) 85 { 86 dfs_f[i + 1][j] = 1; 87 if (dfs(i + 1, j, i2, j2)) 88 { 89 struct node* p = new struct node; 90 p->i = i; 91 p->j = j; 92 dfs_s.s[++dfs_s.top] = *p; 93 delete p; 94 return true; 95 } 96 } 97 if (dfs_f[i][j + 1] == 0 && g[i][j + 1] == 0) 98 { 99 dfs_f[i][j + 1] = 1; 100 if (dfs(i, j + 1, i2, j2)) 101 { 102 struct node* p = new struct node; 103 p->i = i; 104 p->j = j; 105 dfs_s.s[++dfs_s.top] = *p; 106 delete p; 107 return true; 108 } 109 } 110 if (dfs_f[i - 1][j] == 0 && g[i-1][j] == 0) 111 { 112 dfs_f[i - 1][j] = 1; 113 if (dfs(i - 1, j, i2, j2)) 114 { 115 struct node* p = new struct node; 116 p->i = i; 117 p->j = j; 118 dfs_s.s[++dfs_s.top] = *p; 119 delete p; 120 return true; 121 } 122 } 123 if (dfs_f[i][j-1] == 0 && g[i][j-1] == 0) 124 { 125 dfs_f[i][j - 1] = 1; 126 if (dfs(i, j - 1, i2, j2)) 127 { 128 struct node* p = new struct node; 129 p->i = i; 130 p->j = j; 131 dfs_s.s[++dfs_s.top] = *p; 132 delete p; 133 return true; 134 } 135 } 136 return false; 137 } 138 void deep(int i1, int j1, int i2, int j2) 139 { 140 dfs_s.top = -1; 141 for (int i = 0; i < 10; i++) 142 for (int j = 0; j < 10; j++) 143 dfs_f[i][j] = 0; 144 dfs(i1, j1, i2, j2); 145 if (dfs_s.top == -1) 146 { 147 cout << "Error"; 148 } 149 else 150 { 151 while (dfs_s.top != -1) 152 { 153 struct node* ptemp = &dfs_s.s[dfs_s.top--]; 154 cout << "(" << ptemp->i << "," << ptemp->j << ")"; 155 if (dfs_s.top != -1) 156 { 157 cout << "->"; 158 } 159 } 160 } 161 162 } 163 164 void bfs(int s_i, int s_j, int e_i, int e_j) 165 { 166 int err_flag = 0; 167 int f[10][10] = { 0 };//标记是否被访问过 168 struct que q; 169 q.r = q.f = -1; 170 struct node* p = new struct node; 171 p->i = s_i; // start 172 p->j = s_j; 173 p->pre = -1; 174 f[p->i][p->j] = 1; 175 q.s[++q.f] = *p; 176 while (q.r < q.f) 177 { 178 ++q.r; 179 int i = q.s[q.r].i; 180 int j = q.s[q.r].j; 181 if (i == e_i && j == e_j) 182 { 183 break; //到达终点,退出循环 184 } 185 if (g[i][j - 1] == 0 && f[i][j - 1] == 0) 186 { 187 struct node* p = new struct node; 188 p->i = i; 189 p->j = j - 1; 190 p->pre = q.r; 191 f[i][j - 1] = 1; 192 q.s[++q.f] = *p; 193 delete p; 194 } 195 if (g[i - 1][j] == 0 && f[i - 1][j] == 0) 196 { 197 struct node* p = new struct node; 198 p->i = i - 1; 199 p->j = j; 200 p->pre = q.r; 201 f[i - 1][j] = 1; 202 q.s[++q.f] = *p; 203 delete p; 204 } 205 if (g[i][j + 1] == 0 && f[i][j + 1] == 0) 206 { 207 struct node* p = new struct node; 208 p->i = i; 209 p->j = j + 1; 210 p->pre = q.r; 211 f[i][j + 1] = 1; 212 q.s[++q.f] = *p; 213 delete p; 214 } 215 if (g[i + 1][j] == 0 && f[i + 1][j] == 0) 216 { 217 struct node* p = new struct node; 218 p->i = i + 1; 219 p->j = j; 220 p->pre = q.r; 221 f[i + 1][j] = 1; 222 q.s[++q.f] = *p; 223 delete p; 224 } 225 } 226 Stack s; 227 s.top = -1; 228 s.s[++s.top] = q.r; // 终点入栈 229 if (q.s[q.r].i != e_i || q.s[q.r].j != e_j) 230 { 231 cout << "Error"; 232 } 233 else 234 { 235 struct node* p1 = &q.s[q.r]; 236 while (p1->pre != -1) 237 { 238 s.s[++s.top] = p1->pre; 239 p1 = &q.s[p1->pre]; 240 } 241 while (s.top != -1) 242 { 243 cout << "(" << q.s[s.s[s.top]].i << "," << q.s[s.s[s.top]].j << ")"; 244 if (s.top != 0) 245 cout << "->"; 246 s.top--; 247 } 248 } 249 }