一、广搜原理
这里需要用到------队列！
题目：农夫要抓牛，农夫可以向前走一步，向后走一步，向前走x步（x为农夫坐标)，求最短走几次可以走到牛的坐标。
模板：
1、为了方便，定义一个结构体，代表当前x(坐标),steps(走了多少步)
2、创建一个结构体队列a，queue<point> a;
2、将起点,即农夫坐标加入队列，此时队列只有一个元素，编号1。
3、取出队列头元素，将其扩展。将所有队头元素走一步能到达的元素加入队列。在这里就是分别把x=x+1,steps=steps+1和x=x-1,steps=steps+1和x=2*x,steps=steps+1加入队列，分别标号为2，3，4。此时队列中包括队头有四个元素。
4、用queue.pop()方法删除头元素，因为接下来我们要处理下一个元素啦！删除队头后，队列中只有2，3，4，则我们再取队头2，进行扩展。
5、重复第三步。
6、每次取队头元素判断队头的x是否为牛的坐标，如果是，目的达到，返回队头元素对应的steps即为结果！！！
当然，在以上扩展过程中，用vis[]数组标记下个点有没有被走过。因为以第一次扩展就标记了该点，所以以后经过该点都不会继续扩展，即储存了达到该点的最小距离！！！
二、那我们来道题目练习一下吧！！
题目：鸣人和佐助
已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？
输入
输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10
后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。
输出
输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。
这道题目大家先自己做一遍再来看解析，解析在代码块的下面。
#include <bits/stdc++.h>
using namespace std;
struct pos
{
int x,y,cha,t;//坐标为x,y,查克拉为cha,时间为t。
pos(int xx, int yy, int kk, int tt) : x(xx), y(yy), cha(kk), t(tt) {}//快捷入队方式，不是必须操作
};
int vis[209][209],m,n,t,o[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//vis为每个点拥有的最大查克拉
char b[209][209];//储存迷宫
bool judge(int q,int w)//判断扩展时是否越界
{
if(q>=0&&q<=m-1&&w>=0&&w<=n-1)
return true;
else
return false;
}
queue<pos> a;//创建队列
void dfs()
{
while(!a.empty())
{
pos ans=a.front();
a.pop();
if(b[ans.x][ans.y]=='+')
{
cout<<ans.t<<endl;
return;
}
for(int i=0;i<4;i++)//开始扩展！！！
{
int xx=ans.x+o[i][0],yy=ans.y+o[i][1];
if(judge(xx,yy)&&ans.cha>vis[xx][yy])//只有当当前查克拉大于该点时才继续扩展
{
if(b[xx][yy]=='#'&&ans.cha>0)//为‘#'就消耗一个查克拉嘛
{
a.push(pos(xx,yy,ans.cha-1,ans.t+1));
vis[xx][yy]=ans.cha;
}
if(b[xx][yy]!='#')
{
vis[xx][yy]=ans.cha;
a.push(pos(xx,yy,ans.cha,ans.t+1));
}
}
}
}
cout<<-1;//找不到就返回-1
return;
}
int main()
{
cin>>m>>n>>t;
for(int i=0;i<m;i++)
cin>>b[i];
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
vis[i][j]=-1;//初始时每个点都应该可以走，所以都初始化为-1
if(b[i][j]=='@')
{
a.push(pos(i,j,t,0));
vis[i][j]=t;//该点的最大查克拉已知，直接添加
}
}
}
dfs();
return 0;
}
注意
不难发现，这道题目有个坑点，你不能用vis标记地图某个点走没走过!!!
走过的路还可以重复走，因为限制你的不是一面墙，而是你的查克拉多少！！只有把查克拉最大的情况考虑到，才能说一定走不到。不然你可以试试下面这组数据：
10 10 1
@#********
*******###
******##
******##
******##
******##
******##
******##
******##
*******##+
如果按照原来标记的话，（0，2）会被最快的一种走法，一直往右走走过，此时查克拉标记为0，那么永远也走不到终点。当另一种走法绕过起点旁的#时，此时步数远大于2，即使查克拉为1，但是已经被标记为走过，不会再扩展。详细过程可以看上面的代码。