假设有一个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;
}

  

最新文章

  1. SSM项目搭建(提供源码)
  2. python - socket - connection
  3. scala控制结构
  4. Docker 存储设置
  5. Android一体式(沉浸式)状态栏的实现
  6. ubuntu 安装 nodejs
  7. iOS开发中一些常见的并行处理(转)
  8. Configure Puppet Master with Passenger and Apache on Centos
  9. Linux CPU相关信息查看
  10. 问题.NETwebservice其他电脑无法使用-测试窗体只能用于来自本地计算机的请求
  11. 2.RxJava详解网址http
  12. R语言的数据结构
  13. 【转载】VS2010+VMWare8+VisualDDK1.5.6 创建并调试驱动程序 - 完全教程
  14. C语言:XML学习
  15. HDU 5775 Bubble Sort
  16. markdown 字体颜色
  17. 译《Time, Clocks, and the Ordering of Events in a Distributed System》
  18. Python之while循环
  19. JAVA 注解,泛型,反射获取泛型,并实例化
  20. Partition by使用

热门文章

  1. CodeForces D. Concatenated Multiples
  2. hdu 1426 Sudoku Killer (dfs)
  3. 雅礼集训 Day7 T1 Equation 解题报告
  4. 性能优化-FSL(Force Synchronous Layout)强制同步布局
  5. [03] react 测试
  6. C# 代码片段
  7. 使用srvany.exe把程序安装成windows服务
  8. wav格式
  9. linux进程地址空间--vma的基本操作【转】
  10. android与PC直连的socket问题