BFS（宽度优先搜索）
用于求步数最少的解，即深度最小的解
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#define N 201
using namespace std;
//优先队列解决,广度优先
struct Persion
{
int x,y;
int time;
bool operator <(const Persion&t) const
{
return time> t.time; //返回用时最少的
}
};
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char map[N][N];
int visited[N][N];
int m,n;
int BFS(int x,int y)
{
priority_queue <Persion>q;
Persion current,next;
memset(visited,0,sizeof(visited));
current.x=x;
current.y=y;
current.time=0;
visited[current.x][current.y]=1;
q.push(current);
while(!q.empty())
{
current=q.top();
q.pop();
for(int i=0;i<4;i++)
{
next.x=current.x+dir[i][0];
next.y=current.y+dir[i][1];
if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&map[next.x][next.y]!='#'&&!visited[next.x][next.y])
{
if(map[next.x][next.y]=='r')
return current.time+1;
if(map[next.x][next.y]=='x')
next.time=current.time+2;
else
next.time=current.time+1;
visited[next.x][next.y]=1;
q.push(next);
}
}
}
return -1;
}
int main()
{
int i,j;
Persion angle;
while(cin>>n>>m&&(m||n))
{
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cin>>map[i][j];
if(map[i][j]=='a')
{
angle.x=i;
angle.y=j;
}
}
int time=BFS(angle.x,angle.y);
if(time==-1)
cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
else
cout<<time<<endl;
}
return 0;
}
骑士的移动 Knight Moves
https://blog.csdn.net/LD_1090815922/article/details/66995981?depth_1-
注意点：广度优先时遍历时,遍历的不是邻接点,而是国际象棋中马可以走的八个方向.
故定义的偏移量：
int dir[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
#include <bits/stdc++.h>
using namespace std;
char a[5],b[5];
int vis[10][10]; //标记数组，记录已经走过的位置（用bool型也可）
int dir[8][2]= {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};//骑士每次可以移动的八个方向
int sx,sy,ex,ey,t; //sx,sy,es,ey分别代表骑士初始位置和目标位置，t记录走的步数
struct node
{
int x,y,temp;
} s,ns;
void bfs(int x,int y)
{
int i,nx,ny;
queue<node>q; //将队列名设为q；
s.x=x;
s.y=y;
s.temp=0;
vis[x][y]=0;
q.push(s); //将第一个元素加入队列中
while(!q.empty())
{
s=q.front(); //再取出队列中的第一个元素赋值给结构体变量s
q.pop(); //删除第一个元素
if(s.x==ex&&s.y==ey) //判断是否已到达目标位置
{
t=s.temp;
return;
}
for(i=0; i<8; i++) //开始游历查找目标位置
{
nx=s.x+dir[i][0];
ny=s.y+dir[i][1];
if(vis[nx][ny]&&nx>0&&nx<9&&ny>0&&ny<9) //注意是否越界和已游历
{
ns.x=nx;
ns.y=ny;
ns.temp=s.temp+1;
vis[nx][ny]=0; //已经游历就标记为0
q.push(ns); //将下一位置元素压入队列中进行判断
}
}
}
}
int main()
{
while(~scanf("%s%s",a,b))
{
memset(vis,1,sizeof(vis)); //记得每次初始化标记数组
sx=a[0]-'a'+1; //因为输入的是字符，所以需要处理一下。
sy=a[1]-'0';
ex=b[0]-'a'+1;
ey=b[1]-'0';
bfs(sx,sy);
printf("To get from %s to %s takes %d knight moves.\n",a,b,t);
}
return 0;
}
非常可乐
题意： 最终平分的状态是 一个为空 两个平分(可乐最后会倒在最大的两个杯子里面)
#include <bits/stdc++.h>
using namespace std;
int v[5];
int vis[110][110][110];//标记现在三杯水的状态
struct node{
int v[5];//状态 (表示现在水杯里的水杯里的水量)
int cnt;
}temp;
void pour(int a,int b){
int sum=temp.v[a]+temp.v[b];
if(sum>=v[b]) temp.v[b]=v[b];
else temp.v[b]=sum;
temp.v[a] = sum-temp.v[b];
}
void bfs(){
memset(vis,0,sizeof(vis));
queue <node> q;
node cur;
cur.v[1]=v[1];
cur.v[2]=0;
cur.v[3]=0;
cur.cnt=0;
q.push(cur);//把起始状态放在队列里
vis[v[1]][0][0]=1;
while(!q.empty()){
cur = q.front();
q.pop();
if(cur.v[2]==0 && cur.v[3]==cur.v[1]){
printf("%d\n",cur.cnt);
return ;
}
for(int i=1;i<4;i++){
for(int j=1;j<4;j++){
if(i != j ){//不能倒给自己
temp=cur;
pour(i,j);
if(! vis[temp.v[1]][temp.v[2]][temp.v[3]]){
temp.cnt++;
q.push(temp);
vis[temp.v[1]][temp.v[2]][temp.v[3]]=1;
}
}
}
}
}
printf("No\n");
return ;
}
int main(){
while(cin>>v[1]>>v[2]>>v[3]){//各个杯子的容量
if(v[1] ==0 && v[2]==0 && v[3]==0) break;
if(v[2]>v[3]) {//令1 3是最大容量的杯子
int t=v[2];
v[2]=v[3];
v[3]=t;
}
bfs();
}
return 0;
}
奇怪的电梯](https://blog.csdn.net/qq_41431457/article/details/88087660?depth_1-)
#include <bits/stdc++.h>
using namespace std;
int n,s,t;
int a[210];
int vis[210];
struct pos{//状态表示
int level;//此时的位置
int steps;//此时走的步数
};
void bfs(){
pos cur,nex;
cur.level=s;
cur.steps=0;
queue<pos> q;
q.push(cur);
vis[s]=1;
while(!q.empty()){
cur=q.front();
q.pop();
if(cur.level==t){
printf("%d\n",cur.steps);
return;
}
nex.level=cur.level + a[cur.level];
nex.steps=cur.steps + 1;
if(nex.level<=n && vis[nex.level] ==0) {
vis[nex.level] = 1;
q.push(nex);
}
nex.level=cur.level - a[cur.level];
nex.steps=cur.steps + 1;
if(nex.level>=1 && vis[nex.level] ==0) {
vis[nex.level] = 1;
q.push(nex);
}
}
printf("-1\n");
}
int main(){
while(scanf("%d",&n)!=EOF){
if(n == 0) break;
scanf("%d%d",&s,&t);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
vis[i]=0;//初始化
}
bfs();
}
return 0;
}
胜利大逃亡
特殊处理：
if(tx<1||tx>n||ty<1||ty>m||tz<1||tz>k) continue;//越界
if(map[tz][tx][ty]||vis[tz][tx][ty]) continue;//墙或已走过的路
#include<bits/stdc++.h>
using namespace std;
int m,n,k,lim,vis[51][51][51],mapp[51][51][51],ans;
int nxt[6][3]={{1,0,0},{0,1,0},{-1,0,0},{0,-1,0},{0,0,-1},{0,0,1}};//6个方向
struct node {
int x,y,z,step;
};
bool bfs() {
queue<node> q;
q.push(node{1,1,1,0});
while(!q.empty()) {
node tmp=q.front();
q.pop();
if(tmp.x==n&&tmp.y==m&&tmp.z==k) {
ans=tmp.step;
if(ans<=lim) return true;//在限制时间之内逃离迷宫
return false;
}
for(int i=0;i<6;i++) {
int tx=tmp.x+nxt[i][0];//x轴坐标
int ty=tmp.y+nxt[i][1];//y轴坐标
int tz=tmp.z+nxt[i][2];//z轴坐标
if(tx<1||tx>n||ty<1||ty>m||tz<1||tz>k) continue;//越界
if(mapp[tz][tx][ty]||vis[tz][tx][ty]) continue;//墙或已走过的路
q.push(node{tx,ty,tz,tmp.step+1});//步数++
vis[tz][tx][ty]=1;//注意下标顺序
}
}
return false;
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
scanf("%d%d%d%d",&k,&n,&m,&lim);//k块，n行，m列
memset(vis,0,sizeof(vis));
for(int i=1;i<=k;i++)
for(int j=1;j<=n;j++)
for(int u=1;u<=m;u++)
scanf("%d",&mapp[i][j][u]);
if(bfs()) cout<<ans<<endl;
else cout<<"-1"<<endl;
}
return 0;
}
