所以，接着昨天的，我们讲讲剩下两道例题，BFS（类似bfs）题。
题目：
好勒，我先讲讲1333，这是一个类似BFS的题，优化在于：2、3是分别进队的，哪个小哪个进，顺便判个重。因此，我用的是数组模拟，不是queue的stl。
代码：
#include <bits/stdc++.h>
using namespace std;
int a,n;
int q[10000050];//队列
void go(int a,int n)
{
int i=2;
q[1]=a;//第一个是a
int two=1,three=1;
while(i<=n)
{
int w1=q[two]*2+1,w2=q[three]*3+1;//两种方法
int t=min(w1,w2);//取小
if(w1<w2) two++;
else three++;//准备下一个
if(t==q[i-1]) continue;//去重
q[i++]=t;//存入
}
cout<<q[n]<<endl;
}
int main()
{
while(cin>>a>>n) go(a,n);//多组数据，一组一组来
return 0;
}
也有人说用priority做，但会有重复的，不好判重，不然bool数组会特大，这会大到哪呢……
所以比较好做，有种bfs的思路，但是改变的，优化的。
OK，下面讲1335，连通块，纯bfs题，按bfs模板来，怎么做呢，就看代码
#include <bits/stdc++.h>
using namespace std;
bool b[105][105];
int n,m,ans,k,dx[4]= {0,1,0,-1},dy[4]= {1,0,-1,0};//4个方向，应该会背的
struct qq
{
int x3;
int y3;
} w,w1;//结构体，包括两个坐标，用x3、y3是因为y0、y1、y2似乎是在某个函数中的变量，会报错
//x3、y3好弄一点，也怕跟x、y重名，会出现小问题
void bfs(int x,int y)
{
queue<qq> q;//队列
w.x3=x;
w.y3=y;
q.push(w);//推入第一个数的坐标
while(!q.empty())//只要队列非空
{
w1=q.front();//取队首
int nx=w1.x3,ny=w1.y3;//取坐标
q.pop();//弹出队首
for(int i=0; i<4; i++)
{//扩展
w.x3=nx+dx[i];
w.y3=ny+dy[i];
if(w.x3>0&&w.x3<=n&&w.y3>0&&w.y3<=m&&b[w.x3][w.y3])
{ //只要他在区域内，并且没被访问过，且是黑色的
q.push(w);//推入
b[w.x3][w.y3]=0;//标记为不可达的，即访问过的
}
}
}
}//天，这么多后括号
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
cin>>k;
if(k==1)b[i][j]=true;//如果是黑的就表明可达的
}
}//输入
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(b[i][j])//只要可达，就是未被访问过的黑的
{
bfs(i,j);//创造一个新连通块
ans++;
} //逐个排查
}
}
cout<<ans<<endl;//输出解
return 0;
}
这道题就是普通bfs，具体模板，关注我新一文集基础算法，我会写一下的，明天吧。
好勒，两道bfs题就讲到这，只要熟悉模板，学会队列，尝试优化，就能写出优质、成功的代码。
