BFS求最短路
2024-08-25 07:40:54
假设有一个n行m列的迷宫,每个单位要么是空地(用1表示)要么是障碍物(用0表示).如和找到从起点到终点的最短路径?利用BFS搜索,逐步计算出每个节点到起点的最短距离,以及最短路径每个节点的前一个节点。最终将生成一颗以起点为根的BFS树。此时BFS可以求出任意一点到起点的距离。
/*poj3984
---BFS求最短路
--*/
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 5; struct Node{
int x, y;
Node(int a=0, int b=0) :x(a), y(b){}
};
int G[maxn][maxn];
int dis[maxn][maxn];
Node path[maxn][maxn]; const int dir[4][2] = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };
bool isleg(int x, int y){
return (x>=0&& y >= 0 && x < maxn&&y < maxn
&&dis[x][y] == -1&&!G[x][y]);
}
void bfs(){
queue<Node>Q;
Q.push(Node(0, 0));
memset(dis, -1, sizeof(dis));
dis[0][0] = 0;
while (!Q.empty()){
Node u = Q.front(); Q.pop();
for (int i = 0; i < 4; i++){
int dx = u.x +dir[i][0];
int dy = u.y + dir[i][1];
if (isleg(dx, dy)){
dis[dx][dy] = dis[u.x][u.y] + 1;
path[dx][dy] = u;
Q.push(Node(dx, dy));
}
}
}
}
void printPath(Node u){
if (!u.x&&!u.y){
printf("(0, 0)\n");
return;
}
printPath(path[u.x][u.y]);
printf("(%d, %d)\n", u.x, u.y);
}
int main(){
int i, j;
for (i = 0; i < maxn;i++)
for (j = 0; j < maxn; j++)
scanf("%d", &G[i][j]);
bfs();
printPath(Node(4, 4));//printf("%d\n", dis[4][4]);
return 0;
}
最新文章
- SSM项目搭建(提供源码)
- python - socket - connection
- scala控制结构
- Docker 存储设置
- Android一体式(沉浸式)状态栏的实现
- ubuntu 安装 nodejs
- iOS开发中一些常见的并行处理(转)
- Configure Puppet Master with Passenger and Apache on Centos
- Linux CPU相关信息查看
- 问题.NETwebservice其他电脑无法使用-测试窗体只能用于来自本地计算机的请求
- 2.RxJava详解网址http
- R语言的数据结构
- 【转载】VS2010+VMWare8+VisualDDK1.5.6 创建并调试驱动程序 - 完全教程
- C语言:XML学习
- HDU 5775 Bubble Sort
- markdown 字体颜色
- 译《Time, Clocks, and the Ordering of Events in a Distributed System》
- Python之while循环
- JAVA 注解,泛型,反射获取泛型,并实例化
- Partition by使用