题目
test
4
0 0 0 1
0 1 1 0
1 1 1 1
0 0 0 0
1 1 4 3
4
0 0 0 1
0 1 1 0
1 1 1 1
0 0 0 0
1 4 2 4
3
0 1 1
0 0 1
1 0 0
1 1 3 3
BFS解法
一.什么是BFS？
这一节是给不了解BFS同学看的，会的可以跳过(๑╹◡╹)ﾉ"“”。
这层层往外扩散的玩意叫黏菌，没有脑子会走迷宫！！！
感兴趣的同学可以去哔哩哔哩找找。
概念就不多讲了。类似这样层层往外扩散（搜索）就是BFS。
我们做几个小练习
练习1
从左上角开始扩散式一层层填数字。
但是实际上，程序是一步步执行的（一次只能站在一格上出发探索）。
练习2
现在提升一些难度，增加些规则
- 到1格后按照上左下右逆时针的次序探索，标上不同数字（边界外不标）。
- 已经标过数字的不能再标，按照标记的顺序继续探索，直到标满。
从第1个格子探索标序号
后面已经标记过的和超出范围的我就不标黄了
到第3个格子
练习3
从A走到B，用数字标出顺序
我把同一层次的数字标成了相同颜色，看看和你写出来的一样吗
我们走到第10步就能找到出口了。
学会了dfs迷宫找出口的思路，看看核心思路和代码实现
二 .核心思路
- 二维数组表示地图，空地为0，障碍物为1。走过的格子需要标记，避免重复探索。
- 按某个固定顺序依次探索当下格子的四周。将探索到的格子按顺存储起来。
- 按先被存储的格子先行进的顺序，行进到下个格子（先入先出，反手从兜里掏出一个队列）。
- 探索到终点结束。全部格子都遍历过找不到终点结束。
三.代码实现
地图表示，输入，结构体表示yx坐标，队列存储路径等不多讲了
#include<iostream>
#include<queue>
using namespace std;
// 方向增量，分别为yx，用现在坐标加上增量得到后面坐标
int dr[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};// 上下左右
struct Pyx { // 结构体用于存储坐标
int y;
int x;
};
// BFS找出口
string bfs(Pyx start,Pyx end,int (&map)[100][100],int n) {
}
int main() {
int n = 0;// 地图大小
cin>>n;
int map[100][100] = {0};// 地图
for(int i = 0; i<n; i++) {
for(int j = 0; j<n; j++) {
cin>>map[i][j];
}
}
int ha,la,hb,lb;// A和B坐标
cin>>ha>>la>>hb>>lb;
Pyx start,end;// 题目起点是1，1我设的起点0，0，修正一下
start.y = ha-1;
start.x = la-1;
end.y = hb-1;
end.x = lb-1;
cout<<bfs(start,end,map,n);
return 0;
}
声明个变量current存储当下所在位置
探索一下四周，可行进的点存进队列里（存入队列只是表示有记录，不代表走过）。
// BFS找出口
string bfs(Pyx start,Pyx end,int (&map)[100][100],int n) {
if(map[start.y][start.x]||map[end.y][end.x]) {//如果起点或终点是障碍物，不用判定了
return "NO";
}
bool visited[100][100] = {false};// 用于标记地图上的点是否访问过
visited[start.y][start.x] = true;// 将起点标记为已访问
queue<Pyx> path;// 声明一个队列用来储存路径
path.push(start);// 把起点放入队列
Pyx current = path.front();// 表示当下访问的点。
for(int i = 0; i<4; i++) {// 探索4个方向
int next_y = current.y + dr[i][0];
int next_x = current.x + dr[i][1];
if(next_y>=0 && next_y<n && next_x>=0 && next_x<n &&// 限制边界到格子外
// 障碍物不访问。探索到存入队列的不能重复访问。
map[next_y][next_x] == 0 && !visited[next_y][next_x]) {
if(next_y == end.y && next_x == end.x) {// 能从通过检测的点找到终点则退出判定
return"YES";
}
Pyx pyx_next;// 创建节点储存下一步坐标
pyx_next.y = next_y;
pyx_next.x = next_x;
path.push(pyx_next);// 将节点存入队列
visited[next_y][next_x] = true;// 存入队列的，就标记一下免得重复存
}
}
path.pop();// 四个方向探索完，把节点弹出去
}
用一个大循环重复上面的步骤，所有格子都走过后退出。
走过的格子坐标会被弹出队列，即队列为空时退出循环，表示找不到终点。
// BFS找出口
string bfs(Pyx start,Pyx end,int (&map)[100][100],int n) {
if(map[start.y][start.x]||map[end.y][end.x]) {//如果起点或终点是障碍物，不用判定了
return "NO";
}
bool visited[100][100] = {false};// 用于标记地图上的点是否访问过
visited[start.y][start.x] = true;// 将起点标记为已访问
queue<Pyx> path;// 声明一个队列用来储存路径
path.push(start);// 把起点放入队列
while(!path.empty()) {
Pyx current = path.front();// 表示当下访问的点。
for(int i = 0; i<4; i++) {// 探索4个方向
int next_y = current.y + dr[i][0];
int next_x = current.x + dr[i][1];
if(next_y>=0 && next_y<n && next_x>=0 && next_x<n &&// 限制边界到格子外
// 障碍物不访问。探索到存入队列的不能重复访问。
map[next_y][next_x] == 0 && !visited[next_y][next_x]) {
if(next_y == end.y && next_x == end.x) {// 能从通过检测的点找到终点则退出判定
return"YES";
}
Pyx pyx_next;// 创建节点储存下一步坐标
pyx_next.y = next_y;
pyx_next.x = next_x;
path.push(pyx_next);// 将节点存入队列
visited[next_y][next_x] = true;// 存入队列的，就标记一下免得重复存
}
}
path.pop();// 四个方向探索完，把节点弹出去
}
return "NO";// 循环结束了还没找到终点说明到不了
}
完整代码
#include<iostream>
#include<queue>
using namespace std;
// 方向增量，分别为yx，用现在坐标加上增量得到后面坐标
int dr[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};// 上下左右
struct Pyx { // 结构体用于存储坐标
int y;
int x;
};
// BFS找出口
string bfs(Pyx start,Pyx end,int (&map)[100][100],int n) {
if(map[start.y][start.x]||map[end.y][end.x]) {//如果起点或终点是障碍物，不用判定了
return "NO";
}
bool visited[100][100] = {false};// 用于标记地图上的点是否访问过
visited[start.y][start.x] = true;// 将起点标记为已访问
queue<Pyx> path;// 声明一个队列用来储存路径
path.push(start);// 把起点放入队列
while(!path.empty()) {
Pyx current = path.front();// 表示当下访问的点。
for(int i = 0; i<4; i++) {// 探索4个方向
int next_y = current.y + dr[i][0];
int next_x = current.x + dr[i][1];
if(next_y>=0 && next_y<n && next_x>=0 && next_x<n &&// 限制边界到格子外
// 障碍物不访问。探索到存入队列的不能重复访问。
map[next_y][next_x] == 0 && !visited[next_y][next_x]) {
if(next_y == end.y && next_x == end.x) {// 能从通过检测的点找到终点则退出判定
return"YES";
}
Pyx pyx_next;// 创建节点储存下一步坐标
pyx_next.y = next_y;
pyx_next.x = next_x;
path.push(pyx_next);// 将节点存入队列
visited[next_y][next_x] = true;// 存入队列的，就标记一下免得重复存
}
}
path.pop();// 四个方向探索完，把节点弹出去
}
return "NO";// 循环结束了还没找到终点说明到不了
}
int main() {
int n = 0;// 地图大小
cin>>n;
int map[100][100] = {0};// 地图
for(int i = 0; i<n; i++) {
for(int j = 0; j<n; j++) {
cin>>map[i][j];
}
}
int ha,la,hb,lb;// A和B坐标
cin>>ha>>la>>hb>>lb;
Pyx start,end;// 题目起点是1，1我设的起点0，0，修正一下
start.y = ha-1;
start.x = la-1;
end.y = hb-1;
end.x = lb-1;
cout<<bfs(start,end,map,n);
return 0;
}
感兴趣的可以结合着看看另一种dfs解法