# BFS 求最短路

## 1 图

``````1 3  0 21 23
2 0 17 20 22
4 0 14  0  0
5 0 12 15 18
6 8 10  0 19
7 9 11 13 16
``````

## 2 输入

``````6 5
1 1 0 1 1
1 0 1 1 1
1 0 1 0 0
1 0 1 1 1
1 1 1 0 1
1 1 1 1 1
``````

## 3 输出

``````1 2 4 5 6 8 10 12 14 17 20 21 23
12//最短距离
``````

## 4 代码

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 `````` ``````#include #include #include #include #include using namespace std; const int maxn=100+5; int G[maxn][maxn]; //存图的 d=id int path[maxn]; //存每个节点的父节点，即路径 int n,m; //n 行 m 列 int k=1;//记录编号 int end_num; int vx[5] = {-1,1,0,0}; //vx vy 用来计算一个节点周围上下左右 4 个节点 int vy[5] = {0,0,-1,1}; bool vis[maxn][maxn]; //判断某节点是否已经被访问过 struct node { int x; int y; int id; int parent=0; node(int a,int b,int c) { x=a; y=b; id=c; } }; int main() { //freopen("in.txt","r",stdin); memset(G,0,sizeof(G)); memset(vis,0,sizeof(vis)); memset(path,0,sizeof(path)); cin>>n>>m; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { cin>>G[i][j]; } queue q; node v=node(1,1,1); q.push(v); vis[1][1]=1; while(!q.empty()) { node u=q.front(); q.pop(); path[u.id]=u.parent;//记录每个点的父节点 for(int i=0; i<4; i++) { int tx=u.x+vx[i]; int ty=u.y+vy[i]; if(G[tx][ty]&&!vis[tx][ty])//有路可走且未访问 { vis[tx][ty]=1; //cout< ans; //cout<