bfs搜索算法即广度搜索
思路：遍历的过程利用队列存放每一层的元素信息，依次遍历每个元素，返回最短的路径
1 #include <iostream>
2 #include <queue>
3 #include <cstdio>
4 #include <cstring>
5
6 using namespace std;
7
8 //数据结构
9 //存放二维数组的x,y,step步长
10 struct node{
11 int x, y, step;
12 };
13
14 //sx,sy起始地址
15 //ex,ey终止地址
16 int x, y, sx, sy, ex, ey, mark[105][105][2], cnt = 0;
17 int dir[8][2] = {0,1,1,0,0,-1,-1,0,1,1,1,1,-1,-1,1,-1,-1};
18 char mmap[105][105];
19
20 void func(int x, int y){
21 if(mmap[x][y] == 'S') return ;
22 mmap[x][y] = '0';
23 func(mark[x][y][0], mark[x][y][1]);
24
25 }
26
27 void p(){
28 cout << "--------- cnt = " << cnt << "-------------" << endl;
29 for(int i = 1; i <= n; i++){
30 for(int j = 1; j<= m; j++){
31 if(mmap[i][j] == 'x')
32 mmap[i][j] = 'Z';
33 }
34 cout << endl;
35 }
36
37 cout << "--------------------------------------" << endl;
38
39 }
40
41 int main(){
42 cin >> n >> m;
43 for(int i = 1; i <= n; i++){
44 for(int j = 1; j<=m; j++){
45 cin >> mmap[i][j];
46 if(mmap[i][j] == 'S'){
47 sx = i, sy = j;
48 }
49 if(mmap[i][j] == 'T')
50 ex = i, ey = j;
51 }
52 }
53 //创建队列存放每一层的数值
54 queue<node> que;
55 que.push((node){sx, sy, 0});
56 while(!que.empty()){
57 node temp = que.front();
58 que.pop();
59 //方向数组的遍历
60 for(int i = 0; i < 8; i++){
61 int x = temp.x + dir[i][0];
62 int y = temp.y + dir[i][1];
63 //走到终点
64 if(mmap[x][y] == 'T'){
65 func(temp.x, temp.y);
66 p();
67 cout << temp.step + 1 << endl;
68 return 0;
69 }
70 //经过的路径
71 if(mmap[x][y] == '.'){
72 que.push((node){x, y, step.step + 1});
73 mmap[x][y] = 'x';
74 mark[x][y][0] = temp.x, mark[x][y][1] = temp.y;
75 cnt++:
76 if(cnt % 10 == 0)
77 p();
78 }
79 }
80 }
81
82
83 return 0;
84 }
启发式搜索： 利用启发函数缩短搜索的范围，利用优先队列实现最短的搜索路径
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <string>
5 #include <time.h>
6 #include <vector>
7 #include <queue>
8
9 using namespace std;
10
11 struct node{
12 int x,y, step;
13 double dis; //预估距离
14 bool operator<(const node &b) const{
15 return this->step + this->dis > b.step + b.dis;
16 }
17 };
18
19 int n , m, sx, sy, ex, ey, mark[105][105][2], cnt;
20 int dir[8][2] = {0,1,1,0, 0, -1, -1,0, 1,1,1,-1, -1,1,-1,-1};
21 char mmap[105][105];
22
23 double cal(int x, int y){
24 int t1 = ex - x, t2 = ey-y;
25 return sqrt(t1 * t1 + t2 *t2);
26 }
27
28 void func(int x, int y){
29 if(mmap[x][y] == 'S') return ;
30 mmap[x][y] = 'o';
31 func(mark[x][y][0], mark[x][y][1]);
32 }
33
34 void p(){
35 cout << "--------cnt = "<< cnt << "--------" << endl;
36 for(int i = 1; i<=n; i++){
37 for(int j = 1; j<=m; j++){
38 cout << mmap[i][j];
39 if(mmap[i][j] == 'x'){
40 mmap[i][j] = 'Z';
41 }
42 }
43 cout << endl;
44 }
45 cout << "----------------------------------------------"<<endl;
46 }
47
48
49 int main(int argc, char *argv[]){
50 cin >> n >> m;
51 for(int i = 1; i <= n; i++){
52 for(int j = 1; j <= m; j++){
53 cin >> mmap[i][j];
54 if(mmap[i][j] == 'S'){
55 sx = i, sy = j;
56 }
57 if(mmap[i][j] == 'T'){
58 ex = i, ey = j;
59 }
60 }
61 }
62
63 priority_queue<node> que;
64 que.push((node){sx, sy, 0, cal(sx, sy)});
65 while(!que.empty()){
66 node temp = que.top();
67 que.pop();
68 for(int i = 0; i< 8; i++){
69 int x = temp.x + dir[i][0];
70 int y = temp.y + dir[i][1];
71 if(mmap[x][y] == 'T'){
72 func(temp.x, temp.y);
73 p();
74 cout << temp.step + 1 << endl;
75 return 0;
76 }
77
78 if(mmap[x][y] == '.'){
79 mark[x][y][0] = temp.x, mark[x][y][1] = temp.y;
80 que.push((node){x, y, temp.step + 1, cal(x, y)});
81 mmap[x][y] = 'x';
82 cnt++;
83 if(cnt % 10 == 0)
84 p();
85 }
86 }
87 }
88
89 cout << "no"<<endl;
90 return 0;
91 }