2024-01-21自学笔记

2024/1/21 study

1
2
3
4
5
6
7
8
9
10
11
queue<类型>Q;
Q.push(最初状态);
while(!Q.empty()){
	类型 u=Q.front(); Q.pop();
	for(枚举所有可扩展到的状态){
		if(满足入队条件){
			Q.push(状态); //维护某些必要信息 
		}
	} 
} 
//BFS(队列方式)模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//P1135 奇怪的电梯
//借鉴了一下他人告诉我的题面意思（一开始看不懂又想不明白）awa
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
};
int qe[10001];//存放每个层数的信息
int n,a,b;
int ans;
//int ans[101][101];//记录到达每个点需要的步数
bool f[511];//标记已走点
queue<node> q;
int bfs(){
	q.push((node){a,0});//开始入队,从a开始
	f[a]=1;
	while(!q.empty()){//队列不为空
		int x=q.front().x,y=q.front().y;//取队头
		if(x==b) return y;
		q.pop();//提前出队
		int xx=x+qe[x];//上楼
		int yy=y+1;//下楼
		if(xx>=1&&xx<=n&&!f[xx])//如果满足上楼条件
		{
			q.push((node){xx,yy});//入队
			f[xx]=1;
		}
		xx-=2*qe[x];//由于上去了，就要减去
		if(xx>=1&&xx<=n&&!f[xx])//如果满足下楼条件
		{
			q.push((node){xx,yy});//入队
			f[xx]=1;
		}
					
		}
	return -1;
	}
	

signed main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>qe[i];
	}
	printf("%d",bfs());
	return 0;
	
	
}
//禁止抄袭！