BFS(广度优先搜索)
一、介绍
本人学习算法过程中学习到的一些内容。
二、算法模板
关键:要搞清楚求解过程中每一步的相邻状态有哪些,每个状态需要记录什么信息。
#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
typedef struct{
//节点需要保存的信息
}node;
queue<node> q;
int vis[maxn]; //标记是否访问过该节点
int main(){
Node n1,n2;
······
//存储起点信息于n1
q.push(n1);
vis[a]=1;
while(!q.empty()){
n2=q.front();
q.pop();
if(n2符合条件){
//跳出循环,或做相应操作
}
//寻找邻接点,更新n1,加入队列
}
return 0;
}
三、P1135 奇怪的电梯
DFS
#include<bits/stdc++.h>
using namespace std;
typedef struct{
int floor;
int cnt;
}Node;
queue<Node> q;
int n,a,b;
int dis[201],vis[201];
int main(){
Node n1,n2;
scanf("%d %d %d",&n,&a,&b);
for(int i=1;i<=n;i++)
scanf("%d",&dis[i]);
n1.floor=a;
n1.cnt=0;
q.push(n1);
vis[a]=1;
while(!q.empty()){
n2=q.front();
q.pop();
if(n2.floor==b)break;
int i=n2.floor+dis[n2.floor];
if(i<=n&&vis[i]==0){
n1.floor=i;
n1.cnt=n2.cnt+1;
q.push(n1);
vis[i]=1;
}
i=n2.floor-dis[n2.floor];
if(i>=1&&vis[i]==0){
n1.floor=i;
n1.cnt=n2.cnt+1;
q.push(n1);
vis[i]=1;
}
}
if(n2.floor==b)cout<<n2.cnt;
else cout<<-1;
return 0;
}
BFS
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,a,b;
int dis[201];//该层上下移动的层数
bool vis[201];//是否到达过该层
int ans=INF;
int flag;
void dfs(int i,int cnt){
//i为当前楼层,cnt为按按钮的次数
if(vis[i])return;
if(i==b){
ans=min(cnt,ans);
flag=1;
return;
}
if(cnt<=ans){//剪枝
vis[i]=1;//变换位置之后会出现错误
if(i-dis[i]>0)
dfs(i-dis[i],cnt+1);
if(i+dis[i]<=n)
dfs(i+dis[i],cnt+1);
vis[i]=0;
}
}
int main(){
scanf("%d %d %d",&n,&a,&b);
for(int i=1;i<=n;i++)
scanf("%d",&dis[i]);
dfs(a,0);
if(flag)
printf("%d\n",ans);
else
cout<<-1;
return 0;
}