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;
}