~~ 本来想着偷懒不学BFS了直接去学dp，结果发现BFS是dp非常重要的基础
好吧其实是因为24计算概论A期中的B卷最后一题星轨罗盘考察了BFS，本人完全没有任何头绪只能构建完最基本的模块后破防。
有点后悔自己没有从初中开始打oi了，现在真是啥也不会… ~~ 初中那么闲，完全可以打一打NOIP啊
于是我们先从一道简单的《马的遍历》开始解构BFS的思想，并最终解决《星轨罗盘》问题
问题引入：马的遍历
P1443 马的遍历
题目描述
有一个 n x m的棋盘，在某个点 (x, y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数，分别为 n, m, x, y。
输出格式
一个 n x m的矩阵，代表马到达某个点最少要走几步（不能到达则输出 -1）。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
数据规模与约定
对于全部的测试点，保证 1<=x<=400，1<=y<=m<=400。
2022 年 8 月之后，本题去除了对输出保留场宽的要求。为了与之兼容，本题的输出以空格或者合理的场宽分割每个整数都将判作正确。
这是一道最经典的BFS题目。我们不适用数据结构相关，即（queue，set）等内容，仅仅使用至多二维数组解决问题
首先，我们使用一个m x n的bool的二维数组来确定这里是否已经被访问过
随后我们使用一个四行的二维数组作为表格，前两格存储所经之处 第三格存储这格是从哪里跳来的 第四格存储截至目前一共跳了多少次
并且定义head与tail，head是大的循环钟现在开始尝试往四周跳的初始格，tail是小的目前跳到的 这两个均为对应于和存储在第二个二维数组中。
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<bits/stdc++.h>
using namespace std;
int main(){
int m,n;
int x,y;
cin>>m>>n;
int dx[10]={-2,-1,1,2,-2,-1,2,1};
int dy[10]={-1,-2,-2,-1,1,2,1,2};
cin>>x>>y;
for(int p=1;p<=m;p++){
for(int q=1;q<=n;q++)
{
int head=1;
int tail=1;
vector<vector<bool>> M(m+10,vector<bool>(n+10,0));
vector<vector<int>> N(m*n+1000,vector<int>(5,0));
int tx,ty;
N[1][0]=x;
N[1][1]=y;
bool out=0;
if(x==p&&y==q){
cout<<0<<" ";
out=1;
}
else
{
while(head<=tail&&out==0)
{
int nx=N[head][0];
int ny=N[head][1];
for(int i=0;i<8;i++)
{
tx=nx;
ty=ny;
if(tx+dx[i]>=1&&tx+dx[i]<=m&&ty+dy[i]>=1&&ty+dy[i]<=n)
{
if(M[tx+dx[i]][ty+dy[i]]==0)
{
M[tx+dx[i]][ty+dy[i]]=1;
tx+=dx[i];
ty+=dy[i];
tail++;
N[tail][0]=tx;
N[tail][1]=ty;
N[tail][2]=head;
N[tail][3]=N[head][3]+1;
if(tx==p&&ty==q)
{
cout<<N[tail][3]<<" ";
out=1;
}
}
}
}
head++;
}
}
if(!out)cout<<-1<<" ";
}
cout<<endl;
}
return 0;
}
|
但是TLE，因为其实这么做很蠢，相当于是做pq遍 查找一个的最短路径 的问题，但实则没必要重复pq遍bfs，只需要进行一次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
51
52
53
| #include <bits/stdc++.h>
using namespace std;
int main() {
int m, n;
int x, y;
cin >> m >> n;
int dx[10] = {-2, -1, 1, 2, -2, -1, 2, 1};
int dy[10] = {-1, -2, -2, -1, 1, 2, 1, 2};
cin >> x >> y;
int head = 1;
int tail = 1;
vector<vector<bool>> M(m + 10, vector<bool>(n + 10, 0));
vector<vector<int>> N(m * n + 1000, vector<int>(5, 0));
vector<vector<int>> Final(m + 10, vector<int>(n + 10, -1));
int tx, ty;
N[1][0] = x;
N[1][1] = y;
bool out = 0;
while (head <= tail && out == 0) {
int nx = N[head][0];
int ny = N[head][1];
for (int i = 0; i < 8; i++) {
tx = nx;
ty = ny;
if (tx + dx[i] >= 1 && tx + dx[i] <= m && ty + dy[i] >= 1 && ty + dy[i] <= n) {
if (M[tx + dx[i]][ty + dy[i]] == 0) {
M[tx + dx[i]][ty + dy[i]] = 1;
tx += dx[i];
ty += dy[i];
tail++;
N[tail][0] = tx;
N[tail][1] = ty;
N[tail][2] = head;
N[tail][3] = N[head][3] + 1;
Final[tx][ty]=N[tail][3];
}
}
}
head++;
}
Final[x][y]=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cout<<Final[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
|
成功AC
终于可以写去年期中最后一题了
星轨罗盘
星轨罗盘
题目描述
小北喜欢玩游戏，但在星穹铁道这款游戏中，小北遇到了一个难题。
现有一个罗盘，分为内、中、外三圈，每圈有一个指针指在不同的角度，有多种可用的操作可供选择，每种操作可能会有多个圈以不同角度一起旋转，我们的目的是将三层罗盘的指针全部还原到0°位置，试找出最少需要几步可以将罗盘还原。
关于输入
输入包含若干行。
第一行为3个数字，分别代表内、中、外三个罗盘指针的初始位置（0°-359°）。
第二行一个整数n，代表共有n种旋转操作，n≤3。
接下来n段数据，每段有若干行。
其中每段第一行为一个整数mi（1≤mi≤3，1≤i≤n），mi代表当前旋转操作影响的罗盘数。
接下来mi行，每行2个整数，分别代表当前旋转操作具体影响哪个罗盘（0为内圈，1为中圈，2为外圈），以及该罗盘旋转度数（±60，±120，±180，±240，正数代表顺时针，负数代表逆时针）。
关于输出
输出共1行，为最少需要几次操作可以将罗盘还原，保证一定有解。
例子输入
1
2
3
4
5
6
7
8
| 120 0 240
3
1
0 120
1
1 120
1
2 120
|
例子输出
先给出我在学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
51
52
53
54
55
| #include<bits/stdc++.h>
using namespace std;
int minnum=114514;
vector<int> opreation0(vector<int> M, vector<vector<int>> O){
M[0]+=O[0][0];
M[1]+=O[0][1];
M[2]+=O[0][2];
M[0]%=360;
M[1]%=360;
M[2]%=360;
return M;
}
vector<int> opreation1(vector<int> M, vector<vector<int>> O){
M[0]+=O[1][0];
M[1]+=O[1][1];
M[2]+=O[1][2];
M[0]%=360;
M[1]%=360;
M[2]%=360;
return M;
}
vector<int> opreation2(vector<int> M, vector<vector<int>> O){
M[0]+=O[2][0];
M[1]+=O[2][1];
M[2]+=O[2][2];
M[0]%=360;
M[1]%=360;
M[2]%=360;
return M;
}
int main(){
vector<int> M(3,0);
cin>>M[0]>>M[1]>>M[2];
int n,num=0;
vector<vector<int>> O(3,vector<int> (3,0));
cin>>n;
for(int i=0;i<n;i++){
int mi;
cin>>mi;
for(int j=0;j<mi;j++){
int temp1,temp2;
cin>>temp1>>temp2;
O[j][temp1]=temp2;
}
}
while(true){
}
return 0;
}
|
使用同样的逻辑列出广搜表N 前三列分别为内 中 外的角度 最后一行是历经了多少次，之前还不小心漏了负数判断会导致数组溢出，于是给出vector zheng 函数来进行避免负数。
于是又代码
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include<bits/stdc++.h>
using namespace std;
bool S[365][365][365]={0};
vector<int> zheng(vector<int> M){
if(M[0]<0)M[0]=360+M[0];
if(M[1]<0)M[1]=360+M[1];
if(M[2]<0)M[2]=360+M[2];
return M;
}
vector<int> opreation0(vector<int> M, vector<vector<int>> O){
M[0]+=O[0][0];
M[1]+=O[0][1];
M[2]+=O[0][2];
M[0]%=360;
M[1]%=360;
M[2]%=360;
return zheng(M);
}
vector<int> opreation1(vector<int> M, vector<vector<int>> O){
M[0]+=O[1][0];
M[1]+=O[1][1];
M[2]+=O[1][2];
M[0]%=360;
M[1]%=360;
M[2]%=360;
return zheng(M);
}
vector<int> opreation2(vector<int> M, vector<vector<int>> O){
M[0]+=O[2][0];
M[1]+=O[2][1];
M[2]+=O[2][2];
M[0]%=360;
M[1]%=360;
M[2]%=360;
return zheng(M);
}
int main(){
vector<int> M(5,0);
cin>>M[0]>>M[1]>>M[2];
if(M[0]==0&&M[1]==0&&M[2]==0){
cout<<0;
return 0;
}
S[M[0]][M[1]][M[2]]=1;
int n;
vector<vector<int>> O(5,vector<int> (5,0));
vector<vector<int>> N(1000,vector<int>(5,0));
cin>>n;
for(int i=0;i<n;i++){
int mi;
cin>>mi;
for(int j=0;j<mi;j++){
int temp1,temp2;
cin>>temp1>>temp2;
O[i][temp1]=temp2;
}
}
int head=1,tail=1;
N[1][0]=M[0];
N[1][1]=M[1];
N[1][2]=M[2];
N[1][3]=0;
while(head<=tail){
for(int i=0;i<=2;i++){
vector<int> M1=N[head];
if(i==0){
M1=opreation0(M1,O);
}
if(i==1){
M1=opreation1(M1,O);
}
if(i==2){
M1=opreation2(M1,O);
}
if(!S[M1[0]][M1[1]][M1[2]]){
tail++;
S[M1[0]][M1[1]][M1[2]]=1;
N[tail][0]=M1[0];
N[tail][1]=M1[1];
N[tail][2]=M1[2];
N[tail][3]=N[head][3]+1;
}
if(M1[0]==0&&M1[1]==0&&M1[2]==0){
cout<<N[tail][3];
return 0;
}
}
head++;
}
return 0;
}
|
成功AC《星轨罗盘》
使用queue
但是上述使用vector的BFS一是占用内存空间较大，而且逻辑容易混乱，我们应当引入queue来打造正统广搜，懒得重构代码了，我们引入新的一道题
P1135 奇怪的电梯
题目背景
感谢 yummy 提供的一些数据。
题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。
大楼的每一层楼都可以停电梯，而且第 i 层楼（1 ≤ i ≤ N）上有一个数字 K_i（0 ≤ K_i ≤ N）。
电梯只有四个按钮：开，关，上，下。
上下的层数等于当前楼层上的那个数字。
当然，如果不能满足要求，相应的按钮就会失灵。
例如：3, 3, 1, 2, 5 代表了 K_i（K₁=3，K₂=3，……），从 1 楼开始。
在 1 楼，按“上”可以到 4 楼，按“下”是不起作用的，因为没有 -2 楼。
那么，从 A 楼到 B 楼至少要按几次按钮呢？
输入格式
共两行。
第一行为三个用空格隔开的正整数，表示 N, A, B（1 ≤ N ≤ 200，1 ≤ A, B ≤ N）。
第二行为 N 个用空格隔开的非负整数，表示 K_i。
输出格式
一行，即最少按键次数。若无法到达，则输出 -1。
输入输出样例 #1
输入 #1
5 1 5
3 3 1 2 5
输出 #1
3
说明/提示
对于 100% 的数据，1 ≤ N ≤ 200，1 ≤ A, B ≤ N，0 ≤ K_i ≤ N。
本题共 16 个测试点，前 15 个每个测试点 6 分，最后一个测试点 10 分。
给出代码
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
| #include<bits/stdc++.h>
using namespace std;
int main(){
int n,a,b;
cin>>n>>a>>b;
int num=-1;
vector<int> M(n+10,0);
vector<bool> list(n+10,false);
queue<pair<int,int>> q;
for(int i=1;i<=n;i++){
cin>>M[i];
}
if(a==b) {
cout<<0;
return 0;}
q.push({a,0});
while(!q.empty()){
auto [m,t]=q.front();
q.pop();
if(!list[m]){
list[m]=true;
if(m-M[m]>=1){
q.push({m-M[m],t+1});
if(m-M[m]==b){
num=t+1;
break;
}
}
if(m+M[m]<=n){
q.push({m+M[m],t+1});
if(m+M[m]==b){
num=t+1;
break;
}
}
}
}
cout<<num;
return 0;
}
|
成功AC
总的来说广搜还是还可以的
