11-29-2019学习记录

昨天看了一下广度意义上的深度遍历(dfs) 今天接着学到了广度意义上的广度优先遍历(bfs)

这种广度优先遍历在实际意义上与图中深度遍历优先是类似的

dfs隐含的利用了栈(递归),bfs则是利用了队列

这道题便是利用bfs的一道题每次从栈中弹出元素都会把它上下左右四个方向检测将未访问可达的元素入栈

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 #define INF 1000000
 5 #define Max_n 100
 6 #define Max_m 100
 7 typedef pair<int, int> P;
 8 char maze[Max_n][Max_m];
 9 int N, M;
10 int sx, sy;
11 int ex, ey;
12 int Dist[Max_n][Max_n];
13 int dx[4] = { -1,0,1,0 };
14 int dy[4] = { 0,1,0,-1 };
15 int bfs(){
16     for (int i = 0; i < N; i++)
17         for (int j = 0; j < M; j++)
18             Dist[i][j] = INF;
19     queue<P> S;
20     Dist[sx][sy] = 0; //将始点距离置为0
21     S.push(P(sx, sy));//将始点入栈
22     while (S.size()){
23         P p = S.front(); S.pop();
24         if (p.first == ex && p.second == ey)break;//检测是否到达终点
25         else{
26             for (int i = 0; i < 4; i++){
27                 //得到新的位置
28                 int nx = p.first + dx[i];
29                 int ny = p.second + dy[i];
30                 //检测位置是否合法 且可通和未访问
31                 if (nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] != '#' && Dist[nx][ny] == INF){
32                     Dist[nx][ny] = Dist[p.first][p.second] + 1;
33                     S.push(P(nx, ny));
34                 }
35             }
36         }
37     }
38     return Dist[ex][ey];
39 }
40 void solve(){
41     int min = bfs();
42     cout << min;
43 }
44 //读入数据
45 int main()
46 {
47     cin >> N >> M;
48     for (int i = 0; i < N; i++)
49         for (int j = 0; j < M; j++)
50             cin >> maze[i][j];
51     cin >> sx >> sy >> ex >> ey;
52     solve();
53     return 0;
54 }
55 
56 /*
57 10 10
58 #S######.#
59 ......#..#
60 .#.##.##.#
61 .#........
62 ##.##.####
63 ....#....#
64 .#######.#
65 ....#.....
66 .####.###.
67 ....#...G#
68 0 1
69 9 8
70 */

View Code

dfs和bfs都是属于枚举的方法

接着书上提到了贪心

贪心是遵循某种规则不断贪心地选取当前最优策略地想法

书上给了几道很好地例题来体现硬币问题区间问题字典序最小问题

再接着讲到了动态规划(dynamic programming)

提到了背包问题利用记忆化搜索将已经处理过的情况记录