本题是新加入我们的大虾Gabriel童鞋写的,他是一个刚入大学的大一新生,孺子如虎也,赞!
Description
定义一个二维数组:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径,格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
关于BFS算法:
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
解题思路:
该题目是找寻最短路径,要想做出这道题,只需要解决2个问题:
1)找到一条最短路;
2)打印出来。
当然从起点到终点有不止一条路,找到一条最短路就是我们主要需要解决的问题
怎样才算最短的呢?也就是步数最少的,那么我们就可以用BFS搜索解决。
BFS搜索的基本思路为:
按步数搜索,也就是我们从起点开始,找到这个点的所有可能走到的点,这些点就为走一步能到的点。
然后再把所有的走一步能走到的点,再寻找它下一步能走到的点,一直循环重复直到找到终点,那就是从起点能到终点的最短路径了,然后再把每一步的路径存储,搜索完过后打印出来,就能解决问题了。
源码:G++
#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
// 定义的一个结构体w,x和y表示一个点的坐标
typedef struct point_s
{
int x;
int y;
} point_t;
/* 定义一个结构体二维数组
father[x][y].x存的是最短路径的坐标为(x,y)点的下一个坐标的横坐标x
father[x][y].y存的是最短路径的坐标为(x,y)点的下一个坐标的纵坐标y */
point_t father[6][6];
//一个5X5的二维数组表示地图
int maze[5][5];
/* 因为是找最短的路径,所以之前走过的路不能再走,当visited[X][Y]=0时,
表示之前没走过(x,y)这个点,同理,为1时,表示走过 */
int visited[6][6];
/*每一个点能走上下左右4个方向
move[1][0]表示向下走时x坐标该加的值(x+1)
move[1][1]表示向下走时y坐标该加的值(y不变)
move[2][0],move[2][1]表示向右走时,x和y对应的坐标变化
*/
int move[4][2] = {1, 0, 0, 1, 0, -1, -1, 0};
int check(int x, int y) //定义一个检查函数,来检查能不能走到(x,y)这个点,能返回1,不能返回0;
{
/* 能走到这个点满足的条件有
1:该点没被走过,对应的代码是 visited[x][y]==0
2:该点不是墙,是路,对应的代码是 maze[x][y]==0
3:该点 属于5X5的这个迷宫内部,对应的代码是 x<=4&&y<=4&&x>=0&&y>=0
*/
if (visited[x][y] == 0 && maze[x][y] == 0 && x <= 4
&& y <= 4 && x >= 0 && y >= 0) {
//当以下3点满足时,返回1,表示能走到这个点
return 1;
}
//如果前面没有return,代表不能走到这个点,于是返回0
return 0;
}
//主要的BFS搜索函数
void bfs()
{
//定义2个w结构体,point1表示第一个点,point2表示由point1这个点走到的一个点
point_t point1, point2;
//我们选择从右下角忘前面搜,搜到左上角就结束,所以第一个点为(4,4)
point1.x = 4;
point1.y = 4;
//定义一个结构体队列q
queue<point_t> q;
//将第一个点(4,4)加入队列
q.push(point1);
// 当这个队列没空时,就一直循环
while (!q.empty())
{
//取出队列的首端并赋值给point1结构体
point1 = q.front();
//删除队列的首端元素
q.pop();
//当point1为(0,0)时,说明找到了出口,函数结束
if (point1.x == 0 && point1.y == 0)
break;
// 临时变量
int i, tmp_x, tmp_y;
//因为一个点可能能走4步,所以i从0到3,4次循环
for (i = 0; i < 4; i++)
{
tmp_x = point1.x + move[i][0];
//(tmp_x,tmp_y)表示由point1这个点可能 能够走到的所有点
tmp_y = point1.y + move[i][1];
//检查(tmp_x,tmp_y)这个点到底能不能走到,上面有check函数的解释
if (check(tmp_x, tmp_y))
{
//把(tmp_x,tmp_y)这个点赋给point2
point2.x = tmp_x;
point2.y = tmp_y;
//更新father结构体数组中的数据,该数组的意义上面有解释
father[point2.x][point2.y].x = point1.x;
father[point2.x][point2.y].y = point1.y;
//把point2这个点赋为1,表示走过该点
visited[point2.x][point2.y] = 1;
//把point2这个点放进队列中
q.push(point2);
}
}
}
}
//打印答案的函数
void printf()
{
//起点为(0,0)
int x = 0, y = 0;
//当坐标不为(4,4)时,也就是当没走到右下角时,一直循环
while (!(x == 4 && y == 4))
{
//打印该点坐标,最开始打印(0,0)
printf("(%d, %d)\n", x, y);
//tmp_x,tmp_y表示最短路径时(x,y)这个点的下一个点的坐标
int tmp_x, tmp_y;
//赋值给tmp_x,tmp_y
tmp_x = father[x][y].x;
tmp_y = father[x][y].y;
//现在的(x,y)就是这个循环中打印的那个(x,y)的走到的下一个点坐标
x = tmp_x;
y = tmp_y;
}
// 当(x,y)为(4,4)时退出循环,
//当然也要打印最后一个点
printf("(%d, %d)\n", x, y);
}
int main()
{
int i, j;
//输入迷宫maze
for (i = 0; i < 5; i++)
{
for (j = 0; j < 5; j++)
scanf("%d", &maze[i][j]);
}
// 将visited数组全部赋值为0,表示最开始都没走过
for (i = 0; i < 6; i++)
{
for (j = 0; j < 6; j++)
visited[i][j] = 0;
}
//搜索
bfs();
//打印答案
printf();
return 0;
}