海北高端网站建设,浙江网商银行电话,网站要怎么样做排名才上得去,c 做网站怎么截取前面的字符目录 1 基础知识2 模板3 工程化 1 基础知识
BFS可以用来求取最短路#xff0c;前提条件是所有边的权重一样。
2 模板
题目1#xff1a;走迷宫#xff0c;从左上角走到右下角#xff0c;求最短路。
#include iostream
#include queue
#include cstr… 目录 1 基础知识2 模板3 工程化 1 基础知识
BFS可以用来求取最短路前提条件是所有边的权重一样。
2 模板
题目1走迷宫从左上角走到右下角求最短路。
#include iostream
#include queue
#include cstringusing namespace std;const int N 110;
int d[N][N];
int g[N][N];
int n, m;int bfs() {memset(d, -1, sizeof d);queuepairint,int q;q.push({0,0});d[0][0] 0;int dir[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}};while (!q.empty()) {auto t q.front();q.pop();//t下一步可以走到哪儿for (int k 0; k 4; k) {int x t.first dir[k][0], y t.second dir[k][1];if (x n || x 0 || y m || y 0) continue;if (g[x][y] 1) continue;if (d[x][y] ! -1) continue;d[x][y] d[t.first][t.second] 1;q.push({x,y});}}return d[n-1][m-1];
}int main() {cin n m;for (int i 0; i n; i) {for (int j 0; j m; j) {cin g[i][j];}}cout bfs() endl;return 0;
}扩展写法输出最短路的路径。
#include iostream
#include queue
#include cstringusing namespace std;const int N 110;
int d[N][N];
int g[N][N];
int n, m;
pairint,int before[N][N]; //存储前一个结点int bfs() {memset(d, -1, sizeof d);queuepairint,int q;q.push({0,0});d[0][0] 0;int dir[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}};while (!q.empty()) {auto t q.front();q.pop();//t下一步可以走到哪儿for (int k 0; k 4; k) {int x t.first dir[k][0], y t.second dir[k][1];if (x n || x 0 || y m || y 0) continue;if (g[x][y] 1) continue;if (d[x][y] ! -1) continue;d[x][y] d[t.first][t.second] 1;before[x][y] t;q.push({x,y});}}//输出最短路的路径int i n - 1, j m - 1;while (i | j) {cout i i , j j endl;pairint,int t before[i][j];i t.first;j t.second;}return d[n-1][m-1];
}int main() {cin n m;for (int i 0; i n; i) {for (int j 0; j m; j) {cin g[i][j];}}cout bfs() endl;return 0;
}3 工程化
暂无。。。
