22 广度优先搜索（BFS）
理论说明
题目来源和说明
九度OJ
题目描述
Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.魔王住在一个城堡里,城堡是一个ABC的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1.
输入说明
输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它们分别代表城堡的大小和魔王回来的时间.然后是A块输入数据(先是第0块,然后是第1块,第2块......),每块输入数据有B行,每行有C个正整数,代表迷宫的布局,其中0代表路,1代表墙。
输出说明
对于每组测试数据,如果Ignatius能够在魔王回来前离开城堡,那么请输出他最少需要多少分钟,否则输出-1.
样例展示
输入：
1
3 3 4 20
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1
1 0 0 1
0 1 1 1
0 0 0 0
0 1 1 0
0 1 1 0
输出：
11
问题分析
在这个题中，有一个三维的迷宫，每个迷宫的点都用三维坐标（x,y,z）表示。主人公每次行走仅能走到上下左右前后与主人公所在点相邻的位置，即从（x,y,z）点行走到（x-1,y,z）,(x+1,y,z),(x,y+1,z),(x,y-1,z),(x,y,z+1),(x,y,z-1)六个点的其中一个。在这其中还存在着一些墙，主人公在任何情况下都不能走到墙所在的位置上。求从点（0，0，0）走到点（A-1,B-1,C-1）最小需要几步。
最短路：肯定想到了BFS。 BFS往往是解决最短路问题。
这里提供一个BFS的模板框架：
queue<T> Q;
//初始状态进入队列Q
Q.push(T0);
while(Q.empty()==false） {
T now=Q.front();//取队头
Q.pop();
//依次遍历Q当前状态的下一步操作
for(....) {
T t;//下一步新状态
if(mark[t]==true]) continue; //判断死否已经被访问
Q.push(t); //t放进队列
mark[t]=true;//标记表示已访问
if(t==终点) return 需要的信息（比如长度）；
}
}
return -1; //若所有的状态被查找玩，仍然到不了终点，则返回-1
C++代码
#include<iostream>
#include<queue>
using namespace std;
using namespace std;
bool mark[50][50][50]; //标记是否被访问
int maze[50][50][50];
struct T{ //状态结构体
int x,y,z;
int t;
T(int a,int b,int c,int d){
x=a;y=b;z=c;t=d;
}
};
queue<T> Q; //队列，队列中的元素为状态
int go[][3]={
{1,0,0},
{-1,0,0},
{0,1,0},
{0,-1,0},
{0,0,1},
{0,0,-1}
};
int bfs(int a,int b,int c) {
//初始态
T temp(0,0,0,0);
Q.push(temp);
mark[0][0][0]=true;
while(Q.empty()==false) {
T now=Q.front();
Q.pop();
for(int i=0;i<6;i++) {
int nx=now.x+go[i][0];
int ny=now.y+go[i][1];
int nz=now.y+go[i][2];
if(nx<0 || nx>=a || ny<0 || ny>=b || nz<0 || nz>=c) continue;
if(maze[nx][ny][nz]==1) continue;
if(mark[nx][ny][nz]==true) continue;
T temp(nx,ny,nz,now.t+1);
Q.push(temp);
mark[nx][ny][nz]=true;
if(nx==a-1 && ny==b-1 && nz==c-1) return temp.t;
}
}
return -1;
}
int main() {
int m;
scanf("%d",&m);
while(m--) {
int a,b,c,t;
scanf("%d%d%d%d",&a,&b,&c,&t);
for(int i=0;i<a;i++) {
for(int j=0;j<b;j++) {
for(int k=0;k<c;k++) {
scanf("%d",&maze[i][j][k]);
mark[i][j][k]=false;
}
}
}
while(Q.empty()==false) Q.pop();
int res=bfs(a,b,c);
if(res<=t) printf("%d\n",res);
else printf("-1\n");
}
return 0;
}
非常可乐
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是 seeyou 却不这么认为。因为每次当 seeyou 买了可乐以后，阿牛就要求和 seeyou 一起分享这一瓶可乐，而且一定要喝的和 seeyou 一样多。但 seeyou 的手中只有两个杯子，它们的容量分别是 N 毫升和 M 毫升 可乐的体积为 S （S<101）毫升(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M， 101＞S＞0， N＞0， M＞0) 。聪明的 ACMER 你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
输入：
三个整数 : S 可乐的体积 , N 和 M 是两个杯子的容量，以"0 0 0"结束。
输出：
如果能平分的话请输出最少要倒的次数，否则输出"NO"。
样例
输入：
7 4 3
4 1 3
0 0 0
输出：
NO
3
题目分析
这个是一个非常能够说明状态搜索含义的例题，在该例题中，题目中丝毫没有涉及到图的概念，也没有给出任何地图模型。那么它也能进行搜索么？答案是肯定的，收索的途径即是对状态进行搜索。
与第一题一样，我们使用四元组（x,y,z,t）来表示一个状态，其中x,y,z分别表示三个瓶子中的可乐体积，t表示从初始状态到该状态所需的杯子间互相倾倒的次数。状态间的相互扩展，就是任意四元组经过瓶子间的相互倾倒而得到若干组新的四元组的过程。这样平分的状态第一次被搜索出来以后，其状态中表示的被子倾倒次数就是所求。
C++代码
//本题还是用bfs大框架做，只是扩展状态的时候for循环用不了了，可以直接用罗列可用扩展状态，比如这里我就罗列了六种
#include<iostream>
#include<queue>
using namespace std;
bool mark[101][101][101];
struct T{
int x,y,z;
int t;
T(int a,int b,int c,int d) {
x=a,y=b,z=c,t=d;
}
};
queue<T> Q;
void AtoB(int &a,int sa,int &b,int sb) {
//倾倒函数，由容积为sa的杯子倒往容积为sb的杯子
if(sb-b>=a) {
b+=a;
a=0;
}
else {
a-=sb-b;
b=sb;
}
}
int bfs(int s,int n,int m) {
//初始状态
T temp(s,0,0,0);
Q.push(temp);
mark[s][0][0]=true;
while(Q.empty()==false) {
T now=Q.front();
Q.pop();
int a,b,c; //a b c临时保存三个杯子中可乐的体积
a=now.x;
b=now.y;
c=now.z;
AtoB(a,s,b,n); //a倾倒向b
if(mark[a][b][c]==false) {
mark[a][b][c]=true;
T temp(a,b,c,now.t+1);
if(a==s/2 && b==s/2) return temp.t;
if(a==s/2 && c==s/2) return temp.t;
if(c==s/2 && b==s/2) return temp.t;
Q.push(temp);
}
a=now.x;
b=now.y;
c=now.z; //重置
AtoB(a,s,c,m);//a倒向c
if(mark[a][b][c]==false) {
mark[a][b][c]=true;
T temp(a,b,c,now.t+1);
if(a==s/2 && b==s/2) return temp.t;
if(a==s/2 && c==s/2) return temp.t;
if(c==s/2 && b==s/2) return temp.t;
Q.push(temp);
}
a=now.x;
b=now.y;
c=now.z; //重置
AtoB(b,n,a,s);//b倒向a
if(mark[a][b][c]==false) {
mark[a][b][c]=true;
T temp(a,b,c,now.t+1);
if(a==s/2 && b==s/2) return temp.t;
if(a==s/2 && c==s/2) return temp.t;
if(c==s/2 && b==s/2) return temp.t;
Q.push(temp);
}
a=now.x;
b=now.y;
c=now.z; //重置
AtoB(b,n,c,m); //b倒向c
if(mark[a][b][c]==false) {
mark[a][b][c]=true;
T temp(a,b,c,now.t+1);
if(a==s/2 && b==s/2) return temp.t;
if(a==s/2 && c==s/2) return temp.t;
if(c==s/2 && b==s/2) return temp.t;
Q.push(temp);
}
a=now.x;
b=now.y;
c=now.z; //重置
AtoB(c,m,a,s);
if(mark[a][b][c]==false) {
mark[a][b][c]=true;
T temp(a,b,c,now.t+1);
if(a==s/2 && b==s/2) return temp.t;
if(a==s/2 && c==s/2) return temp.t;
if(c==s/2 && b==s/2) return temp.t;
Q.push(temp);
}
a=now.x;
b=now.y;
c=now.z; //重置
AtoB(c,m,b,n);
if(mark[a][b][c]==false) {
mark[a][b][c]=true;
T temp(a,b,c,now.t+1);
if(a==s/2 && b==s/2) return temp.t;
if(a==s/2 && c==s/2) return temp.t;
if(c==s/2 && b==s/2) return temp.t;
Q.push(temp);
}
}
return -1;
}
int main() {
int s,n,m;
while(scanf("%d%d%d",&s,&n,&m)!=EOF) {
if(s==0) break;
if(s%2==1) {
puts("NO");
continue;
}
for(int i=0;i<=s;i++) {
for(int j=0;j<=n;j++) {
for(int k=0;k<=m;k++) {
mark[i][j][k]=false;
}
}
}
//清空队列中的状态
while(Q.empty()==false) Q.pop();
int res=bfs(s,n,m);
if(res==-1) {
puts("NO");
}
else {
printf("%d\n",res);
}
}
return 0;
}
Leetcode题目太多，不知道如何准备高校夏令营？欢迎关注本专栏，和本小白一起准备夏令营吧！ 本专题的规划如下： 截止到4月下旬：以王道考研为依托，提供夏令营机考的准备计划，打好基础 截止到5月中旬：以剑指offer进一步加强 本专题的内容如下： 1. 给出题目的在线测试链接，方面您检查代码的正确性 2. 给出题解
百度成长空间 523人发布
投递字节跳动等公司6个岗位