BFS③

· · 算法·理论

vector与pair

首先，我们来学习一下STL（标准模板库）里的 vector 与 pair。

vector 是动态数组，也就是 vector 的空间大小不是固定的，是可变化的。

首先，我们来学习几个最基础的操作：

vector<数据类型> 变量名 就能创建一个动态数组。

比如说：vector<int> a 表示创建了一个数据类型为 int，变量名为 a 的动态数组。

a.push_back(x) 表示在动态数组 a 的末尾插入 x。

a[i] 可以访问下标为 i 的元素，注意：动态数组的下标从 0 开始。

a[i]=x 表示把动态数组 a 中下标为 i 的位置修改为 x。

那么，在 a_i 还没有元素时能正常访问吗？

我们运行这个代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int main(){
    cout<<a[0];
    return 0;
}

结果显示：

没有任何输出，并出现了RE的情况。

为了避免这种情况，出现了 resize 函数。

a.resize(n) 表示将 a 的大小设为 n，并将里面全部填充为 0。

a.resize(n,x) 表示将 a 的大小设为 n，并将里面全部填充为 x。

我们再运行这个代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int main(){
    a.resize(10);
    cout<<a[0];
    return 0;
}

就能正常输出了。

另外，还有一些比较常用的函数，大家可以自行尝试。

a.size() 可以快速获取 a 数组的大小，一般用于遍历整个数组。

a.insert(a.begin()+i,x) 可以在下标 i 前面插入 x。

a.erase(a.begin()+i) 可以删除下标为 i 的元素。

sort(a.begin(),a.end()) 可以将整个数组排序。

我们来做一个例题：

F1501 【入门】数组存数

我们来学习一下如何创建一个二维动态数组：

vector<int> a[114514] 表示创建 114154 个动态数组。

而我们可以用 sort 与 size 函数来求解这道题

#include<bits/stdc++.h>
using namespace std;
vector<int> a[100005];
int n,m;
int main(){
    cin>>n>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
    }for(int i=1;i<=n;i++){
        sort(a[i].begin(),a[i].end());
        cout<<a[i].size()<<" ";
        for(int j=0;j<a[i].size();j++){
            cout<<a[i][j]<<" ";
        }cout<<"\n";
    }
    return 0;
}

pair 可以看成只有两个元素的结构体，创建方法为 pair<int> a。

其中第一个元素为 a.first，第二个为a.second。

我们可以创建一个 pair 类型的动态数组，其创建方法为：vector<pair<int,int>> a。

那我们来猜一猜，如何插入元素进动态数组呢？

a.push_back(x,y)？a.push_back({x,y})？都错了！

我们要用到一个名字叫 make_pair 的函数，插入方法为 a.push_back(make_pair(x,y))。

奇怪，我们明明是来学BFS的，怎么讲了这么多STL呢？

当然是为了迎接我们的大BOSS，有传送门的迷宫问题了。

有传送门的迷宫问题（不能跳过传送门，进传送门无价值）

我们直接来说思路：

我们按照正常的广搜来写，当往四个方向遍历时遇到传送门时，就找到另一个传送门，队列里插入它的下标。

那么，传送门要不要标记是否走过了呢？

如上图，我们需要从起点走入传送门，传送后走入空地再走入传送门，最后进入终点。

由此可见，传送门不能标记。

在存储传送门下标时，我们可以用一个 pair 类型的二维动态数组。

是不是听着有点晕？我们直接走入例题，通过代码来理解。

P1825 [USACO11OPEN] Corn Maze S

根据上面的内容，直接给出代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[305][305];
bool vis[305][305];
int sx,sy,ex,ey;
vector<pair<int,int>> o[30];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct kkk{
    int x,y,step;
};
int bfs(){
    queue<kkk> q;
    q.push({sx,sy,0});
    vis[sx][sy]=1;
    while(!q.empty()){
        kkk u=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=u.x+dx[i],yy=u.y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){
                if(c[xx][yy]>='A'&&c[xx][yy]<='Z'){
                    vector<pair<int,int>> w=o[c[xx][yy]-'A'];
                    int x=w.size();
                    for(int j=0;j<x;j++){
                        if(xx!=w[j].first||yy!=w[j].second){
                            q.push({w[j].first,w[j].second,u.step+1});
                            if(w[j].first==ex&&w[j].second==ey){
                                return u.step+1;
                            }
                        }
                    }
                }else{
                    q.push({xx,yy,u.step+1});
                    vis[xx][yy]=1;
                    if(xx==ex&&yy==ey){
                        return u.step+1;
                    }
                }
            }
        }
    }   
    return -1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
            if(c[i][j]=='@'){
                sx=i;
                sy=j;
            }if(c[i][j]=='='){
                ex=i;
                ey=j;
            }if(c[i][j]>='A'&&c[i][j]<='Z'){
                o[c[i][j]-'A'].push_back(make_pair(i,j));
            }if(c[i][j]=='#'){
                vis[i][j]=1;
            }
        }
    }cout<<bfs();
    return 0;
}