例题小引——迷宫问题
问题描述:
迷宫由n行m列的单元格组成(n，m都小于等于50），每个单元格要么是空地，要么是障碍物。
现请你找到一条从起点到终点的最短路径长度。
分析——（迷宫问题BFS解法）
- 使用BFS算法，进行广度优先遍历，总体思路是访问一个结点，就把相邻的结点入队，然后下一个访问的结点就是队首结点，依此循环到终点
- 相邻结点的判断：由于上述迷宫只能上下左右四个方向，因此设计坐标轴，上下左右按照坐标增减来确定坐标
代码
#include <bits/stdc++.h>
using namespace std;
int field[100][100];
bool visited[100][100]={false};
struct point{
int x;
int y;
int step;
};
queue<point> info;//结点信息队列
int direct_x[4] = {-1,1,0,0};//方向：上下左右
int direct_y[4] = {0,0,-1,1};
int main()
{
//输入
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&field[i][j]);
}
}
int start_x,start_y,end_x,end_y;
scanf("%d%d%d%d",&start_x,&start_y,&end_x,&end_y);
//BFS
point start;
start.step = 0;
start.x = start_x;
start.y = start_y;
info.push(start);
visited[start_x][start_y] = true;
bool flag = false;
while(info.empty()!=true){
int x = info.front().x;
int y = info.front().y;
if(x==end_x&&y==end_y){
printf("%d\n",info.front().step);
flag = true;
break;
}
for(int i=0;i<4;i++){
int temp_x = x+direct_x[i];
int temp_y = y+direct_y[i];
if(field[temp_x][temp_y]==1&&visited[temp_x][temp_y]==false){
point temp;
temp.x = temp_x;
temp.y = temp_y;
temp.step = info.front().step +1;
info.push(temp);
visited[temp_x][temp_y]==true;
}
}
info.pop();//队首出队
}
if(flag==false){
printf("no way");
}
return 0;
}
迷宫问题使用BFS的总结
需要定义的重要数组
- 迷宫地图：二维数组 f i e l d [ m ] [ n ] field[m][n] field[m][n]，其中 m m m是行数， n n n是列数
- 已访问标记：二维bool数组 v i s i t e d [ m ] [ n ] visited[m][n] visited[m][n]
- 地址信息：结构体，需要包含该地址的横纵坐标和到达此处走的步数
- 指路队列：以地址信息为数据类型的队列，每次离开一个地址之前，先要把接下来能够去的地址信息入队
- 方向数组：两个数组 d i r e c t x [ w a y s ] direct_x[ways] directx[ways]和 d i r e c t y [ w a y s ] direct_y[ways] directy[ways]，ways表示在一个地址处能够移动的方向个数，数组存的是如果按照这个方向走，其横纵坐标变化情况
初始化
- 输入迷宫信息初始化迷宫地图
- 根据出发点信息，创建地址信息结点加入队列，初始时的步数是0
- 初始时地图上所有结点都未访问，访问标记设为false
BFS启动
- 当指路队列非空时，重复操作1~4，如果空，跳到5.
- 根据指路队列首结点，即当前的位置（横纵坐标），判断是否到达终点，如果到达跳到5.，没有到达执行3
- 遍历查看所有的ways个方向指向的地址能不能到达，如果可以到达，那么将该地址入队
- 所有能走的路都计入队列后，离开当前地址，跳到1.
- 判断：如果是从1跳过来的，说明终点不可达；如果是从2跳过来的，说明终点可达，且当前队首所指地址信息的步数就是从起点到终点的总步数
小试牛刀——石油储藏（中国科学院大学2021年机试题）
分析
- 按照行列顺序遍历地图，一旦找到‘@’，那么就以此地址作为起点，进行BFS：
- BFS：对于沿途所有能到达的地址，如果该地址是‘@’，那么就置为’*'，同时设置为已访问
- 每完成一次BFS就表明一个连续的油田已经被勘测完毕，油田计数器+1
- 遍历完地图，油田计数器值即为地图上油田数
代码
#include <cstdio>
#include <map>
#include <string>
#include <string.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <limits.h>
using namespace std;
char field[101][101];
bool visited[101][101]={false};
struct address{
int x;
int y;
};
int direct_x[8] = {-1,-1,-1,0,1,1, 1, 0};
int direct_y[8] = {-1, 0, 1,1,1,0,-1,-1};
queue<address> instructor;
void BFS(int x, int y){
address start;
start.x = x;
start.y = y;
field[x][y] = '*';
visited[x][y] = true;
instructor.push(start);
while(instructor.empty()!=true){
int x = instructor.front().x;
int y = instructor.front().y;
for(int i=0;i<8;i++){
int temp_x = x+direct_x[i];
int temp_y = y+direct_y[i];
if(field[temp_x][temp_y]=='@'&&visited[temp_x][temp_y]==false){
address temp;
temp.x = temp_x;
temp.y = temp_y;
field[temp_x][temp_y]='*';
visited[temp_x][temp_y]=true;
instructor.push(temp);
}
}
instructor.pop();
}
}
int main(){
int m,n;
while(true){
scanf("%d%d ",&m,&n);
if(m==0&&n==0){
break;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
scanf("%c",&field[i][j]);
visited[i][j]=false;//多次输入，随输入进行初始化
}
scanf("%c",&field[i][0]);
}
/*for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
printf("%d\t%d\t%c\n",i,j,field[i][j]);
}
printf("\n");
}*/
int counts = 0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(field[i][j]=='@'){
BFS(i,j);
counts++;
}
}
}
printf("%d\n",counts);
}
return 0;
}