首页 > itarticle > 蓝桥杯省赛学习第四周记录（广度优先搜索）

蓝桥杯省赛学习第四周记录（广度优先搜索）

admin 11月 14, 2020 0

开学了,每天上课耽误不少时间…好想带着电脑去上课呀qwq.
个人认为广度优先搜索要比深度优先搜索难一些，难在需要借助很多数据结构来解决问题

核心思想

个人认为广度优先搜索的核心思想是队列

在一切开始之前，首先要学会队列的用法：

数据结构的特性就不说了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 


//定义
queue<int> q; //这里定义了一个数据类型为整形的队列
//向队列中添加元素
q.push();
//删除队列元素
q.pop();
//获得队列元素个数
q.size();
//判断队列是否为空
q.empty();
//清空整个队列
while(!q.empty()){
  q.pop();
}

广度优先搜索的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void (起始点) {
    将起始点放入队列中;
    标记起点访问;
    while (如果队列不为空) {
        访问队列中队首元素x;
        删除队首元素;
        for (x 所有相邻点) {
            if (该点未被访问过且合法) {
                将该点加入队列末尾;
            }
        }
    }
    队列为空，广度优先搜索结束;
}

只看模板会让人看得一头雾水，其简单来说就是：

  • 每次将当前访问的结点从队列中拿出来
  • 检查他所能直接到达的结点并将它们入队
  • 此结点出队
  • 再从队列中取出首部结点循环操作，直到队伍中不再含有任何结点，此时广度搜索结束

每次将当前访问结点的直接后继结点入队，体现了广度优先搜索的过程

最简单的广度优先搜索：再探走迷宫

1
2
3
4
5
6
 
5 6
....S*
.**...
.*..*.
*..**.
.T....

第一行输入为地图的大小，之后是地图的样式。
要求输出到达终点的最小步数，如果无法到达终点，输出-1

因为是广度优先搜索，所以第一次达到终点时的步数就是最小步数
对于每个结点，定义一个结构体struct

1
2
3
4
5
6
7
8
9
10
 
//x,y为该结点的下标，d为搜索到此结点时的步数
//这里为了结点入队时的初始化参数，定义一个构造函数
struct node{
    int x, y, d;
    node(int xx, int yy, int dd){
        x = xx;
        y = yy;
        d = dd;
    }
};

另外为了防止重复访问（避免在两块地板之间来回走），与深度优先搜索一样，需要定义一个bool型数组存储是否访问过这块地板

1
 
bool vis[110][110];

下面给出源码，程序的各部分功能已在代码中给出注释

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
 
#include <iostream>
#include <string>

using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; //遍历的四个方向
bool in(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}
struct node{
    int x, y, d;
    node(int xx, int yy, int dd){
        x = xx;
        y = yy;
        d = dd;
    }
};
int (int sx, int sy){
    queue<node> q;         //创建队列
    q.push(node(sx, sy, 0));
    vis[sx][sy] = true;
    while(!q.empty()){
        node now = q.front();   //获得队首结点
        q.pop();                //队首出队
        for(int i = 0; i < 4; i++){
            int tx = now.x + dir[i][0];
            int ty = now.y + dir[i][1];
            if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
                if(maze[tx][ty] == 'T'){   //如果访问到终点，返回此结点的步长
                    return now.d + 1;
                }
                else{                     //如果当前结点的直接后继结点没有被访问过且不是墙*,标记访问并将此结点入队
                    vis[tx][ty] = true;
                    q.push(node(tx, ty, now.d + 1));
                }
            }
        }
    }
    return -1;  //所有能够到达的结点都已访问过，此时队列为空，根据题意返回-1
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }
    int x, y;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (maze[i][j] == 'S') {
                x = i, y = j;
            }
        }
    }
    cout << bfs(x, y) << endl;
    return 0;
}

简单例题

一维坐标

avatar
只是比走迷宫抽象了一点点，这里的每个节点分为三个方向，分别访问并将能访问到的结点入队即可

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
 
#include <iostream>

using namespace std;
bool vis[5005];
int n, A, B;
int m = 5005;
struct node{
    int x, d;
    node(int xx, int dd){
        x = xx;
        d = dd;
    }
};
bool in(int x){
    return x >= 0 && x <= n;
}
void (int x, int d){
    queue<node> q;
    q.push(node(x, d));
    while(!q.empty()){
        node now = q.front();
        q.pop();
        int nx;
        nx = now.x + 1;
        if(in(nx) && !vis[nx]){
            if(nx == B){
                if(now.d + 1 < m){
                    m = now.d + 1;
                }
            }
            else{
               vis[nx] = true;
                q.push(node(nx, now.d + 1));
            }
        }
		nx = now.x - 1;
        if(in(nx) && !vis[nx]){
            if(nx == B){
                if(now.d + 1 < m){
                    m = now.d + 1;
                }
            }
            else{
               vis[nx] = true;
                q.push(node(nx, now.d + 1));
            }
        }
    	nx = now.x * 2;
        if(in(nx) && !vis[nx]){
            if(nx == B){
                if(now.d + 1 < m){
                    m = now.d + 1;
                }
            }
            else{
               vis[nx] = true;
                q.push(node(nx, now.d + 1));
            }
        }
    }
    return;
}
int main(){
    cin >> n >> A >> B;
    bfs(A, 0);
    cout << m << endl;
}

密码锁

avatar

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
 
#include <iostream>

#include <string>
using namespace std;
int b[4];
int e[4];
bool vis[10][10][10][10];
struct node{
    int num[4];
    int step;
    node(int a, int b, int c, int d, int dd){
        num[0] = a;
        num[1] = b;
        num[2] = c;
        num[3] = d;
        step = dd;
    }
};
int (){
    queue<node> q;
    q.push(node(b[0], b[1], b[2], b[3], 0));
    vis[b[0]][b[1]][b[2]][b[3]] = true;
    while(!q.empty()){
        node now = q.front();
        for(int i = 0; i < 4; i++){
            now.num[i]++;
            if(now.num[i] == 10){
                now.num[i] = 1;
            }
            if(now.num[0] == e[0] && now.num[1] == e[1] && now.num[2] == e[2] && now.num[3] == e[3]){
                return now.step + 1;
            }
            if(!vis[now.num[0]][now.num[1]][now.num[2]][now.num[3]]){
                vis[now.num[0]][now.num[1]][now.num[2]][now.num[3]] = true;
                q.push(node(now.num[0], now.num[1], now.num[2], now.num[3], now.step + 1));
            }
            if(now.num[i] == 1){
                now.num[i] = 9;
            }
            else{
                now.num[i]--;
            }
        }
        for(int i = 0; i < 4; i++){
            now.num[i]--;
            if(now.num[i] == 0){
                now.num[i] = 9;
            }
            if(now.num[0] == e[0] && now.num[1] == e[1] && now.num[2] == e[2] && now.num[3] == e[3]){
                return now.step + 1;
            }
            if(!vis[now.num[0]][now.num[1]][now.num[2]][now.num[3]]){
                vis[now.num[0]][now.num[1]][now.num[2]][now.num[3]] = true;
                q.push(node(now.num[0], now.num[1], now.num[2], now.num[3], now.step + 1));
            }
            if(now.num[i] == 9){
                now.num[i] = 1;
            }
            else{
                now.num[i]++;
            }
        }
        for(int i = 0; i < 3; i++){
            swap(now.num[i], now.num[i + 1]);
            if(now.num[0] == e[0] && now.num[1] == e[1] && now.num[2] == e[2] && now.num[3] == e[3]){
                return now.step + 1;
            }
            if(!vis[now.num[0]][now.num[1]][now.num[2]][now.num[3]]){
                vis[now.num[0]][now.num[1]][now.num[2]][now.num[3]] = true;
                q.push(node(now.num[0], now.num[1], now.num[2], now.num[3], now.step + 1));
            }
            swap(now.num[i], now.num[i + 1]);
        }
        q.pop();
    }
    return -1;
}
int main(){
    int tb;
    int te;
    cin >> tb >> te;
    b[0] = tb / 1000;
    b[1] = (tb / 100) % 10;
    b[2] = (tb / 10) % 10;
    b[3] = tb % 10;
    e[0] = te / 1000;
    e[1] = (te / 100) % 10;
    e[2] = (te / 10) % 10;
    e[3] = te % 10;
    cout << bfs() << endl;
    return 0;
}

与其他数据结构结合的广度优先搜索

一维跳棋

avatar
avatar
这道题难度明显提升，（其实仔细想想还好，就是需要在结构体中用到其他的数据结构来存储一些必要信息）
每个结点用来存储当前的棋盘结构和空格位置
每次在队首拿到新结点时，通过空格的位置来进一步确定下一次移动棋子所能达到的样式
因为最后输出的是整个移动棋子过程中所有的空格位置，所以在结构体中需要定义一个vector数组来存储每次的空格位置，因此，bfs函数的返回类型应该为 vector
另外为了防止重复访问，定义一个映射map：用来记录每一种棋盘情况是否能被访问过。

1
 
map<string, bool> vis

（棋盘结构用string存储）
用swap函数交换棋子和空格的位置，每个结点对应棋子都有四种跳跃方式，分别是两侧与空格不相邻的棋子向空格跳跃，和两侧与空格相邻的棋子向空格移动
很重要的一点：每个结点在每个方向交换棋子和空格位置后，都需要将已交换的妻子和空格复原成此结点最初的样式，便于此结点对应棋子其他形式的改变

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
 
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

#include <cstring>
using namespace std;
int N;
int blank;
string init ="";
string ans ="";
map<string, bool> vis;
vector<int> vinit;
struct node{
    vector<int> b;
	string s;
    node(){}
    node(vector<int> bb, string ss){
        b = bb;
        s = ss;
    }
};
int dir[4] = {1, 2, -1, -2};
vector<int> bfs(){
    queue<node> q;
    vector<int> v;
    string s;
    q.push(node(vinit, init)); //初始棋盘状态入队
    while(!q.empty()){
        s = q.front().s;
        v = q.front().b;
        q.pop();
        blank =  v.size() == 0 ? N : v[v.size() - 1];  //获得当前结点对应棋盘的空格位置
        if(s == ans){   //如果代表棋盘的字符串样式与最终结果相同，返回结点中保存空格位置的vector数组
            return v;
        }
        for(int i = 0; i < 4; i++){
        	int u = blank + dir[i];
            if(u >= 0 && u < N * 2 + 1){
            	swap(s[u], s[blank]); //交换棋子和空格位置
                if(vis.find(s) == vis.end()){
                    vis[s] = 1;
                    v.push_back(u);  //空格位置数组更新
                    q.push(node(v, s));
                    v.pop_back();    //空格位置数组复原
                }
                swap(s[u], s[blank]);//将此方向的交换复原
            }
    	}
    }
}
int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        init += 'W';
        ans += 'B';
    }
    init += ' ' + ans;
    vis[init] = 1;
    ans = init;
	reverse(ans.begin(), ans.end());
    vector<int> vans = bfs();
    for(int i = 0; i < vans.size(); i++){
        if(i % 5 == 4){
            cout << vans[i] + 1 << endl;
        }
        else{
            cout << vans[i] + 1 << ' ';
        }
    }
}

三阶平面魔方

avatar
avatar
用整型数存储魔方样式
同样用一个映射map存储当前魔方样式是否被访问过

1
 
map<int, bool> vis;//当前魔方样式，是否被访问

因为魔方转动时我是用二维数组，代码写起来非常麻烦(..•˘_˘•..)
与其他题目一样，在每个结点中每次交换魔方方块之后不要忘记还原（还原的代码swap应该与旋转魔方方块的代码swap是对称的，而不应相同）
比如下面的swap代码，应该是对称的（我最开始就错在还原的swap顺序写错了，导致没有真正还原）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
//right
for(int i = 0; i < 3; i++){
    swap(map[i][0], map[i][2]);
    swap(map[i][0], map[i][1]);
    aa = map[0][0] * 100 + map[0][1] * 10 + map[0][2];
    bb = map[1][0] * 100 + map[1][1] * 10 + map[1][2];
    cc = map[2][0] * 100 + map[2][1] * 10 + map[2][2];
    vist = aa * 1000000 + bb * 1000 + cc;
    if(vist == 123456789){
        return step + 1;
    }
    if(!vis[vist]){
        vis[vist] = true;
        q.push(node(aa, bb, cc, step + 1));
    }
    swap(map[i][0], map[i][1]);   //还原，先做上面的第二步，与旋转方块的swap对称
    swap(map[i][0], map[i][2]);
}

下面给出源码

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
using namespace std;
int mape[3][3];
map<int, bool> vis;
int a, b, c;
struct node{
    int step;
    int map[3][3];
    node(int a, int b, int c, int vv){
		map[0][0] = a / 100;
        map[0][1] = (a / 10) % 10;
        map[0][2] = a % 10;
        map[1][0] = b / 100;
        map[1][1] = (b / 10) % 10;
        map[1][2] = b % 10;
        map[2][0] = c / 100;
        map[2][1] = (c / 10) % 10;
        map[2][2] = c % 10;
        step = vv;
    }
};
int (){
    queue<node> q;
    int aa, bb, cc;
    int step = 0;
    int vist = 0;
    int map[3][3];
    q.push(node(a, b, c, 0));
    vist = a * 1000000 + b * 1000 + c;
    vis[vist] = true;
    while(!q.empty()){
        step = q.front().step;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                map[i][j] = q.front().map[i][j];
            }
        }
        q.pop();
        //right
        for(int i = 0; i < 3; i++){
            swap(map[i][0], map[i][2]);
            swap(map[i][0], map[i][1]);
            aa = map[0][0] * 100 + map[0][1] * 10 + map[0][2];
            bb = map[1][0] * 100 + map[1][1] * 10 + map[1][2];
            cc = map[2][0] * 100 + map[2][1] * 10 + map[2][2];
            vist = aa * 1000000 + bb * 1000 + cc;
            if(vist == 123456789){
                return step + 1;
            }
            if(!vis[vist]){
                vis[vist] = true;
                q.push(node(aa, bb, cc, step + 1));
            }
            swap(map[i][0], map[i][1]);
            swap(map[i][0], map[i][2]);
        }
		    //left
        for(int i = 0; i < 3; i++){
            swap(map[i][0], map[i][2]);
            swap(map[i][2], map[i][1]);
            aa = map[0][0] * 100 + map[0][1] * 10 + map[0][2];
            bb = map[1][0] * 100 + map[1][1] * 10 + map[1][2];
            cc = map[2][0] * 100 + map[2][1] * 10 + map[2][2];
            vist = aa * 1000000 + bb * 1000 + cc;
            if(vist == 123456789){
                return step + 1;
            }
            if(!vis[vist]){
                vis[vist] = true;
                q.push(node(aa, bb, cc, step + 1));
            }
            swap(map[i][2], map[i][1]);
            swap(map[i][0], map[i][2]);
        }
        //up
        for(int i = 0; i < 3; i++){
            swap(map[0][i], map[2][i]);
            swap(map[0][i], map[1][i]);
            aa = map[0][0] * 100 + map[0][1] * 10 + map[0][2];
            bb = map[1][0] * 100 + map[1][1] * 10 + map[1][2];
            cc = map[2][0] * 100 + map[2][1] * 10 + map[2][2];
            vist = aa * 1000000 + bb * 1000 + cc;
            if(vist == 123456789){
                return step + 1;
            }
            if(!vis[vist]){
                vis[vist] = true;
                q.push(node(aa, bb, cc, step + 1));
            }
            swap(map[0][i], map[1][i]);
            swap(map[0][i], map[2][i]);
        }
        //down
        for(int i = 0; i < 3; i++){
            swap(map[0][i], map[2][i]);
            swap(map[2][i], map[1][i]);
            aa = map[0][0] * 100 + map[0][1] * 10 + map[0][2];
            bb = map[1][0] * 100 + map[1][1] * 10 + map[1][2];
            cc = map[2][0] * 100 + map[2][1] * 10 + map[2][2];
            vist = aa * 1000000 + bb * 1000 + cc;
            if(vist == 123456789){
                return step + 1;
            }
            if(!vis[vist]){
                vis[vist] = true;
                q.push(node(aa, bb, cc, step + 1));
            }
            swap(map[2][i], map[1][i]);
            swap(map[0][i], map[2][i]);
        }
    }
    return -1;
}
int main(){
    cin >> a >> b >> c;
	  mape[0][0] = a / 100;
    mape[0][1] = (a / 10) % 10;
    mape[0][2] = a % 10;
    mape[1][0] = b / 100;
    mape[1][1] = (b / 10) % 10;
    mape[1][2] = b % 10;
    mape[2][0] = c / 100;
    mape[2][1] = (c / 10) % 10;
    mape[2][2] = c % 10;
    cout << bfs() << endl;
}

吃糖的时间

avatar
avatar
同样是麻烦的代码，用二位vector存储每个小朋友与其他小朋友的关系

1
 
vector<int> child[100005];

但是用二维vector存储关系其实有一个严重的问题，比如说关系中某一行的输入为 6 5

1
2
3
4
5
 
int a, b;
for(int i = 0; i < p; i++){
        cin >> a >> b;
        child[a].push_back(b);
    }

这里如果我单纯用二维vector存储关系，只能通过6号小朋友找到5号小朋友，而不能通过5号小朋友找到6好小朋友(最开始我在这里卡了很长时间)
因此在二维vector录入数据时，不仅要child[a].push_back(b); 还需要 child[b].push_back(a);，将两个人的关系在每个人的vector中都体现出来
因为用了bool型数组保存对应小朋友有没有被访问，所以无需考虑重复的问题
下面给出源码

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
 
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
int n, p, c;
int m;
vector<int> child[100005];
bool vis[100005];
struct node {
    int N;    //小朋友的编号
    int step;   //步长
    node(int _n, int _step){
        N = _n;
        step = _step;
    }
};
int bfs(){
    queue<node> q;
    q.push(node(c, 1));
    vis[c] = true;
    int N, step;
    while(!q.empty()){
        N = q.front().N;
        step = q.front().step;
        //cout << N << " " << step << endl;
        q.pop();
        while(child[N].size() != 0){
            if(!vis[child[N][child[N].size() - 1]]){
                vis[child[N][child[N].size() - 1]] = true;
            	q.push(node(child[N][child[N].size() - 1], step + 1)); //找到与当前小朋友相邻且没有被发糖的小朋友，入队。
            }
            child[N].pop_back();
        }
    }
    return step + m;
}
int main(){
	cin >> n >> p >> c;
	cin >> m;
    int a, b;
    for(int i = 0; i < p; i++){
        cin >> a >> b;
        child[a].push_back(b);
        child[b].push_back(a);
    }
    cout << bfs() << endl;
}

难度提高：蒜头回家

avatar
avatar
此题难度进一步提升，需要先拿到钥匙再到达终点
我定义了两个队列，在第一个队列中拿到钥匙，此时将此钥匙结点入队列2，并在队列2中继续广度优先搜索，因为拿到钥匙后可以走拿到钥匙之前已经走过的地板，所以需要新开一个bool型数组，存储拿到钥匙后访问的路径
这里我最开始是在队列2每次访问到终点后将队列2清空，同时将新开的vis2数组值全部改为false，这种方法会超时。
为了节约时间做出以下修改：

  • 在队列2中的遍历，只要步长已经超过此时已经得到过的最小步长，直接清空队列退出
  • 定义一个bool型三维数组用来存储拿到钥匙后的访问路径，省去每次重新为vis2数组赋值的时间

其余部分详情看注释，下面给出源码

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
96
97
 
#include <iostream>
#include <queue>
using namespace std;
int n, m;
char map[2005][2005];
bool vis[2005][2005]; //拿到钥匙前的标记数组
bool vis2[20][2005][2005]; //拿到钥匙后的标记数组
int sx, sy;
int mini = 9999999; //设最小值初始为9999999
int k;
//每个结点的结构，分别为：步长，改点的对应下标
struct node {
    int step;
    int x, y;
    node(int _x, int _y, int _step){
        x = _x;
        y = _y;
        step = _step;
    }
};
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
//判断是否在地图内的函数in
bool in(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < m;
}
void bfs(){
    queue<node> q;
    queue<node> q2;
    q.push(node(sx, sy, 0));
    int nx, ny, step;
    vis[sx][sy] = true;
    while(!q.empty()){
        nx = q.front().x;
        ny = q.front().y;
        step = q.front().step;
        q.pop();
    	if(map[nx][ny] == 'P'){      //拿到钥匙后的操作
            k++;
            q2.push(node(nx, ny, step + 1));
            while(!q2.empty()){
                nx = q2.front().x;
                ny = q2.front().y;
                step = q2.front().step;
                q2.pop();
                if(step > mini){          //如果此时步长已经大于此时的步长最小值，退出
                    while(!q2.empty()){
                        q2.pop();
                    }
                    break;
                }
                if(map[nx][ny] == 'T'){   //拿到钥匙后最终到达终点
                    if(step < mini){      //判断此时步长是否小于最小值，如果小于则交换
                        swap(step, mini);
                    }
                    while(!q2.empty()){   //清空队列2
                        q2.pop();
                    }
                    break;                //退出拿到此钥匙后的广度优先搜索，继续在外循环找下一把钥匙
                }
                for(int i= 0; i < 4; i++){
                    nx = nx + dir[i][0];
                    ny = ny + dir[i][1];
                    if(map[nx][ny] != '#' && in(nx, ny) && !vis2[k][nx][ny]){
                        vis2[k][nx][ny] = true;
                        q2.push(node(nx, ny, step + 1));
                    }
                    nx = nx - dir[i][0];
                    ny = ny - dir[i][1];
                }
            }
        }
        for(int i= 0; i < 4; i++){
            nx = nx + dir[i][0];
            ny = ny + dir[i][1];
            if(map[nx][ny] != '#' && in(nx, ny) && !vis[nx][ny]){
                vis[nx][ny] = true;
                q.push(node(nx, ny, step + 1));
            }
            nx = nx - dir[i][0];
            ny = ny - dir[i][1];
        }
    }
    return;         //搜索完所有的可能，退出
}
int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> map[i][j];
            if(map[i][j] == 'S'){
                sx = i, sy = j;
            }
        }
    }
    bfs();
    cout << mini - 1 << endl;
}

难度再次提升

题太难，时间有限考前先不整理了

未完待续

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能