广搜(三)：STL在广搜算法中的应用
引言：
广度优先搜索是信息奥赛中算法部分的重要内容，而STL是c++中数据结构的主要实现方式，两者相结合会产生什么样的结果呢？本文将介绍STL中的vector与pair与广搜的综合应用。
第一部分: vector与pair简介
关于vector
vector，即动态数组，是与普通数组类似的数据存储结构。然而，与数组不同的是，vector的数组空间是动态的，即其大小不是定值，在需要存入值时便在数组中添加空间。由于这一特性，vector数组通常比较占空间，这点需要格外注意。
下面介绍几个vector的基本操作
1.定义：vector<数据类型> 数组名
这只是基本的定义方式，即定义一个vector数组。还有另外一种定义形式：
vector<数据类型>数组名[N]
这是一个二维的vector数组，即定义了N个vector。
为了方便书写，以下统一使用vector<int>p
2.插入元素：p.push_back(x)
这一句将一个x插入到数组的最后，算法复杂度为
3.访问元素：直接使用下标，注意从0开始
4.清空：p.clear()
5.插入元素到指定位置：p.insert(p.begin()+i,a)
注意，i是下标，该语句将a元素插入到i+1号元素前面
6.删除：p.erase(p.begin()+i)
删除的是第i+1个元素
7.两个resize
p.resize(n) ->改变长度为n，默认初始值是0
p.resize(n,x) ->改变长度为n，全部修改为x
8.排序：sort(p.begin(),p.end())，可以自定义比较器
关于pair
pair，意为“一对”，是含有两个数值的数据结构，因此又名“一对值”，是简易版的结构体。以下是pair的基本操作
1.定义：pair<第一个数据类型，第二个数据类型>名称
以下以pair<int,int>p为例
2.组装：p=make_pair(x,y)，将x和y组装成一对
3.访问元素：
例如，x为p.first,y为p.second,注意不要打括号
下面来看一些类型的题。
第二部分:打印路径问题
原题链接：F1443 【提高】走出迷宫的最短路径
在广搜中打印路径有两种方式：利用递归和利用pair。本文主要介绍后者（递归方法详见广搜(二)）。相比于递归，pair更加直观易懂，但是由于需要vector，其需要的空间大于递归。
这一方法的基本原理是在广搜原有的结构体中加入pair类型的vector数组。每当我们搜到一个点，就利用数组记录下这个点的前驱，最后按先后顺序输出数组即可。
详见代码：
#include<bits/stdc++.h>
using namespace std;
const int N=50;
int n,m,sx,sy,ex,ey;
struct node{
int x,y;
vector<pair<int,int> >path;
};
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool vis[N][N];
int a[N][N];
bool check(int x,int y){
return x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y];
}
void bfs(){
queue<node>q;
vector<pair<int,int> >path1;
path1.push_back(make_pair(sx,sy));//利用临时vector来开辟第一个队列元素
q.push({sx,sy,path1});
vis[sx][sy]=1;
while(!q.empty()){
node u=q.front();
q.pop();
for(int i=0;i<4;i++){
int xx=u.x+dx[i];
int yy=u.y+dy[i];
if(check(xx,yy)){
u.path.push_back(make_pair(xx,yy));//将u.path当作临时中介将xx和yy的信息加入队列
q.push({xx,yy,u.path});
u.path.pop_back();//删除临时元素
if(xx==ex&&yy==ey){
vector<pair<int,int> >path2=u.path;//复制
for(int j=0;j<path2.size();j++){//输出
cout<<"("<<path2[j].first<<","<<path2[j].second<<")->";
}
cout<<"("<<ex<<","<<ey<<")";
exit(0);
}
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]==1) vis[i][j]=1;
}
}
cin>>sx>>sy>>ex>>ey;
bfs();
cout<<"no way";
return 0;
}第三部分:传送门问题
原题链接:P1825 [USACO11OPEN] Corn Maze S
本题看起来不难，但是比正常的走迷宫多出了传送门。当牛走到传送门时必须穿越到另一端，而且可以无限次穿越。那么我们怎么处理这个传送门呢？
首先，我们可以发现，一个传送门最多只需要使用两次，因为两次之后传送门的两端的情况都可以被遍历。其次，当我们遇到传送门时，传送门的两个端点不能标记vis也不能放入队列，因为传送门可能多次使用，如果标记了就会出错。最后是关于传送门的存储与判断。我们可以开一个pair类型的vector数组G[26],用以存储每一个字母所包含的所有传送门的坐标。每当我们遍历时遇到传送门，就在对应字母的vector中寻找与起点不同的传送门进行传送即可。
代码如下：
/*
遇到传送门直接使用(前提是这个传送门必须使用)
传送门最多需要使用两次(不标记)
1.遇到传送门，直接传送
2.传送门传送的下一个点不需要放到队列
记录传送门：
vector <pair<int,int> >G[26];//26个字母G[0]表示A这个传送门需要(x,y)
*/
#include<bits/stdc++.h>
using namespace std;
const int N=350;
char a[N][N];
int n,m;
int sx,sy,ex,ey;
bool vis[N][N];
void spj(int i,int j){
if(a[i][j]=='#') vis[i][j]=1;
if(a[i][j]=='='){
ex=i;ey=j;
}
if(a[i][j]=='@'){
sx=i;sy=j;
}
return;
}
vector<pair<int,int> >G[26];
void get_tp(int i,int j){
if(a[i][j]>='A'&&a[i][j]<='Z'){
G[a[i][j]-'A'].push_back(make_pair(i,j));//找传送门
}
return;
}
struct node{
int x,y,step;
};
queue<node> q;
bool check(int x,int y){
if(x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y]) return 1;
return 0;
}
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int bfs(){
q.push({sx,sy,0});
vis[sx][sy]=1;
while(!q.empty()){
node u=q.front();
q.pop();
int cx=u.x,cy=u.y;
//先找传送门再扩散方向
if(a[cx][cy]>='A'&&a[cx][cy]<='Z'){//寻找传送门终点
int id=a[cx][cy]-'A';
for(int i=0;i<G[id].size();i++){
if(G[id][i].first!=cx||G[id][i].second!=cy){
cx=G[id][i].first;
cy=G[id][i].second;
break;
}
}
}
for(int i=0;i<4;i++){
int xx=cx+dx[i];
int yy=cy+dy[i];
if(check(xx,yy)){
vis[xx][yy]=1;
if(xx==ex&&yy==ey) return u.step+1;
q.push({xx,yy,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>>a[i][j];
spj(i,j);
get_tp(i,j);
}
}
cout<<bfs();
return 0;
}结语：
STL本身是一个十分方便的工具，但是当多种STL嵌套使用时就会变得复杂，如果再和算法相结合就更加复杂。因此，本文涉及的内容虽然思维难度不大，但是代码的细节容易出错。各位读者在写此类题的程序时一定小心，小心，再小心！