BFS求迷宫的最短路径 输出最短路径的步数

[cpp] w plain 

1. #include <iostream>  

2. #include<queue>  

3. using namespace std;  

5. const int INF = 10000000;  

7. typedef pair<int, int> P;//保存状态，即点的位置  

9. //迷宫，'#'表示墙壁， '.'表示通道，S表示起点，G表示终点  

10. char maze[10][10] =   

11. {  

12.     '#','S','#','#','#','#','#','#','.','#',  

13.     '.','.','.','.','.','.','.','#','.','#',  

14.     '.','#','.','#','#','.','#','#','.','#',  

15.     '.','#','.','.','.','.','.','.','.','.',  

16.     '#','#','.','#','#','.','#','#','#','#',  

17.     '.','.','.','.','#','.','.','.','.','#',  

18.     '.','#','#','#','#','#','#','#','.','#',  

19.     '.','.','.','.','#','.','.','.','.','.',  

20.     '.','#','#','#','#','.','#','#','#','.',  

21.     '.','.','.','.','#','.','.','.','G','#'  

22. };  

23. const int N  = 10;  

24. const int M = 10;  

25. int sx = 0, sy = 1; //起点  

26. int gx = 9, gy = 8; //终点  

27. int d[N][M];&nbsp;   //到各点的最短距离数组  

28. int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; //下、右、上、左四个方向移动的向量  

29. int bfs()  

30. {  

31.     queue<P> que;  

32.     //初始化，未访问标记  

33.     for (int i = 0; i < N; i++)  

34.     {  

35.         for (int j = 0; j < M; j++)  

36.         {  

37.             d[i][j] = INF;  

38.         }  

39.     }  

40.     que.push(P(sx, sy));    //起点入队  

41.     d[sx][sy] = 0;  //起点距离为0  

42.     while (que.size())  

43.     {  

44.         P p = que.front();  

45.         que.pop();  

46.         if (p.first == gx && p.second == gy)    //到达终点  

47.         {  

48.             break;  

49.         }  

50.         //  向四个方向移动  

51.         for (int i = 0; i < 4; i++)  

52.         {  

53.             int nx = p.first + dx[i];  

54.             int ny = p.second + dy[i];  

55.             if (nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] != '#' && d[nx][ny] == INF)  

56.             {  

57.                 que.push(P(nx, ny));  

58.                 d[nx][ny] = d[p.first][p.second] + 1;  

59.             }  

60.         }  

62.     }  

63.     return d[gx][gy];  

64. }  

66. int main()  

67. {  

68.     cout << "最短距离：" << bfs() << endl;  

69.     getchar();  

70.     return 0;  

71. }  

该程序可以正常运行。

改进：

// maze.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>  
#include<queue>  
using namespace std;

#define MAXN 100 + 10

int m, n;//m行，n列
//坐标点(x,y)  
//坐标点限制，对于x>=0&&x<m   对于y>=0&&y<n

//设置一个最大值
const int INF = 10000000;

typedef pair<int, int> P;//保存状态，即点的位置  

char maze[MAXN][MAXN];//迷宫

int d[MAXN][MAXN];    //到各点的最短距离数组


//迷宫，'#'表示墙壁， '.'表示通道，S表示起点，G表示终点  
//本题迷宫已经给好，可以手动输入。
//迷宫起始位置，从0，0开始算的。
//char maze[10][10] =
//{ 
//	'#', 'S', '#', '#', '#', '#', '#', '#', '.', '#',//1
//	'.', '.', '.', '.', '.', '.', '.', '#', '.', '#',//2
//	'.', '#', '.', '#', '#', '.', '#', '#', '.', '#',//3
//	'.', '#', '.', '.', '.', '.', '.', '.', '.', '.',//4
//	'#', '#', '.', '#', '#', '.', '#', '#', '#', '#',//5
//	'.', '.', '.', '.', '#', '.', '.', '.', '.', '#',//6
//	'.', '#', '#', '#', '#', '#', '#', '#', '.', '#',//7
//	'.', '.', '.', '.', '#', '.', '.', '.', '.', '.',//8
//	'.', '#', '#', '#', '#', '.', '#', '#', '#', '.',//9
//	'.', '.', '.', '.', '#', '.', '.', '.', 'G', '#'//10
//};    
//#.######.#
//.......#.#
//.#.##.##.#
//.#........
//##.##.####   5
//....#....#
//.#######.#
//....#.....
//.####.###.
//....#....#    10


int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 }; //下、右、上、左四个方向移动的向量  

//x1,y1:起始点   x2,y2终点
int bfs(int x1,int y1,int x2,int y2)
{
	queue<P> que;
	//初始化，未访问标记  
	for (int i = 0; i < m; i++)//m行
	{
		for (int j = 0; j < n; j++)//n列
		{
			d[i][j] = INF;
		}
	}
	que.push(P(x1, y1));    //起点入队  
	d[x1][y1] = 0;  //起点距离为0  
	while (que.size())
	{
		P p = que.front();
		que.pop();
		if (p.first == x2 && p.second == y2)    //到达终点  
		{
			break;
		}
		//  向四个方向移动  
		for (int i = 0; i < 4; i++)
		{
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];

			if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] != '#' && d[nx][ny] == INF)
			{
				que.push(P(nx, ny));
				d[nx][ny] = d[p.first][p.second] + 1;
			}
		}

	}
	return d[x2][y2];
}


int main()
{
	//起点，终点 局部变量
	int startx, starty, goalx, goaly;

	cin >> m >> n;//m行，n列

	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			cin >> maze[i][j];//输入值
	//个整数k, x 1, y 1, x 2, y 2 其中k最多能转的弯数，
	//(x 1, y 1), (x 2, y 2)表示两个位置，其中x 1，x 2对应列，y 1, y 2对应行。
	//cin >> k >> start.y >> start.x >> goal.y >> goal.x;

	cin >> startx >> starty >> goalx >> goaly;//

	cout << "最短距离：" << bfs(startx, starty, goalx, goaly) << endl;
	system("pause");
	return 0;

 

 

推荐使用：

// maze.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>  
#include<queue>  
using namespace std;

#define MAXN 100 + 10

int m, n;//m行，n列
//坐标点(x,y)  
//坐标点限制，对于x>=0&&x<m   对于y>=0&&y<n

//设置一个最大值
const int INF = 10000000;

typedef pair<int, int> P;//保存状态，即点的位置  

char maze[MAXN][MAXN];//迷宫

int d[MAXN][MAXN];    //到各点的最短距离数组


//迷宫，'#'表示墙壁， '.'表示通道，S表示起点，G表示终点  
//本题迷宫已经给好，可以手动输入。
//迷宫起始位置，从0，0开始算的


int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 }; //下、右、上、左四个方向移动的向量  

//x1,y1:起始点   x2,y2终点
int bfs(int x1,int y1,int x2,int y2)
{
	queue<P> que;
	//初始化，未访问标记  
	for (int i = 0; i < m; i++)//m行
	{
		for (int j = 0; j < n; j++)//n列
		{
			d[i][j] = INF;
		}
	}
	que.push(P(x1, y1));    //起点入队  
	d[x1][y1] = 0;  //起点距离为0  
	while (que.size())
	{
		P p = que.front();
		que.pop();
		if (p.first == x2 && p.second == y2)    //到达终点  
		{
			break;
		}
		//  向四个方向移动  
		for (int i = 0; i < 4; i++)
		{
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];

			if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] != '#' && d[nx][ny] == INF)
			{
				que.push(P(nx, ny));
				d[nx][ny] = d[p.first][p.second] + 1;
			}
		}

	}
	return d[x2][y2];
}


int main()
{
	//起点，终点 局部变量
	int startx, starty, goalx, goaly;

	cin >> m >> n;//m行，n列

	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			cin >> maze[i][j];//输入值

	cin >> startx >> starty >> goalx >> goaly;//

	cout << "最短距离：" << bfs(startx, starty, goalx, goaly) << endl;
	system("pause");
	return 0;
}