BFS

解决迷宫问题

迷宫问题

Crawling in process… Crawling failed Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit Status
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

输出

左上角到右下角的最短路径

解题思路

使用结构体来保存横纵坐标即(x,y)，输出没要求距离长度，定义一个step保存长度也可以

创建一个队列 queue q;

1
2
3
4
5
6
7
8
9
10
while(q不为空){
if(到达右下角){
    输出或是退出
}else{
    for(){
         枚举四个方向  合适的就入队
    }
}
q.pop();  //出队列
}

如何输出路径呢？

这里我们使用一个 print() 函数， 在函数内 递归调用 print()函数，直到为左上角就输出，

怎么调用前一个呢？

我们可以再创建一个结构体的二维数组，每个对应位置存放的是，它爸爸的x,y坐标

Step pre[5] [5];

在 q.push(); 的时候 pre[nx] [ny].x = s.x,pre[nx] [ny].y = s.y;

这样pre[][] 当前对应的[nx] [ny]，就应该存放 它爸爸的x,y

输出：

1
2
3
4
5
6
7
8
9
void print(int x,int y){
    if(x == 0 && y == 0){
        printf("(0, 0)\n");
        return;
    }
    print(pre[x] [y].x,pre[x] [y].y);
    printf("(%d, %d)\n",x,y);
    return;
}

代码

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
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
using namespace std;
struct Step{
	int x,y;
	int steps;
};
int a[5][5],book[5][5]={0};
int Next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
queue<Step> q;
Step pre[5][5];
void print(int x,int y){
	if(x==0&&y==0){
		printf("(0, 0)\n");
		return;
	}
	print(pre[x][y].x,pre[x][y].y);
	printf("(%d, %d)\n",x,y);
	return;
}
void bfs(){
	Step nd;
	    nd.x=0,nd.y=0,nd.steps=0; book[0][0] = 1;
	    q.push(nd);
	    while(!q.empty()){
			Step s = q.front();
			if(s.x == 4 && s.y == 4){
				print(4,4);
				break;
			}
			for(int i=0;i<4;i++){
				int nx = s.x + Next[i][0], ny = s.y + Next[i][1], step = s.steps+1;
				if((nx<=4&&nx>=0) && (ny<=4&&ny>=0) && book[nx][ny]==0 && a[nx][ny]==0){
					Step p; p.x=nx,p.y=ny,p.steps=step;
					book[nx][ny] = 1; pre[nx][ny].x = s.x,pre[nx][ny].y = s.y;
					q.push(p);
				}
			}
			q.pop();
		}
}
int main(){
	for(int i=0;i<5;i++)
	    for(int j=0;j<5;j++)
	        cin>>a[i][j];
	bfs();
    return 0;	
}

学习代码

一般来说，是不需要输出图像的。这时，代码可以简化，更便于学习

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
#include <iostream>
#include <queue>
using namespace std;

const int N = 110;
int n, m;
int g[N][N]; // 迷宫
int d[N][N]; // 到起点的距离
bool st[N][N]; // 标记是否已经走过

struct Point {
    int x, y;
};

// 四个方向
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

// BFS模板
int bfs() {
    queue<Point> q;
    q.push({0, 0});
    st[0][0] = true;
    d[0][0] = 0;

    while (q.size()) {
        auto t = q.front();
        q.pop();

        // 如果到达终点，返回距离
        if (t.x == n - 1 && t.y == m - 1) return d[n - 1][m - 1];

        // 四个方向
        for (int i = 0; i < 4; i++) {
            int a = t.x + dx[i], b = t.y + dy[i];

            // 判断是否越界或者障碍物
            if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 0 && !st[a][b]) {
                q.push({a, b});
                st[a][b] = true;
                d[a][b] = d[t.x][t.y] + 1; // 到起点的距离加一
            }
        }
    }

    return -1; // 如果无法到达终点，返回-1
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}