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 }