BFS：抓住那头牛

抓住那头牛

广度优先搜索

首先要给节点分层，起点是第0层，从起点最少要到达1步的点就是第1层。

节点0属于第三层

从2走一步可以到1，从2走一步到4，但4不是第2层的节点，不可以算，之后再考虑4,4再考虑5,5已经走过了，所以从3走到5需要两步

广度优先搜索：
可确保找到最优解，但是因扩展出的节点较多，且多数节点都需要保存，因此需要的存储空间较大，用队列存节点。
我们用广搜的目标节点，我们碰到了目标节点就找到了目标节点的最短路径，如果没有目标节点。

不太好的地方：在解决问题中扩展出的好多节点，需要的存储空间比深度优先搜索更高。

深搜vs.广搜

广搜算法

队列：先进先出
Open表就是一个队列
扩展：从N出发走一步都可以新的节点
放在队列的尾部，可以同时把节点指向父节点的指针引导队列里面去，
从n走一步到达m

变化过程

open表只有一个3，closed表是空
3进入closed表，open表为246，



6出列了，6不可以，不能拿出来了

1出来了

目标节点5出列，问题解决！

5的父节点4，4的父节点3

int N,K;
const int MAXN=100000;//最大的坐标范围
int visited[MAXN+10];//判重标记，visited[i]=true表示i已经扩展过，曾经进入过open表，或者从Open表出来，或者还在open表里面
struct Step{
	int x;//位置
	int stpes;//到达x所需的步数
	Step(int xx,int s):x(xx(,strps(s){}
};
queue<Step> q;//队列，即Open表
int main(){
	cin>>N>>K;
	memset<visited,0,sizeof(visited));
	q.push(Step(N,0));//队列里面放入农夫的起始位置
	visited[N]=1;//农夫站的位置被访问过
	while(！q.empty()){
		Strp s=q.front();//拿出队头的元素
		if(s.x==K){//找到目标
			cout<<s.steps<<endl;
			return 0;
		}else{
				if(s.x-1>=0&&!visited[s.x-1]{//拿出来扩展，如果能往左边走,左边没被访问过
					q.push(Strep(s.x-1,s,steps+1));//把左边节点塞到里面去
					visited[s.x-1]=1;//一个节点放入队列里面，设置这个节点的访问标记
				}
				if(s.x-1>=0&&!visited[s.x-1]{//拿出来扩展，如果能往右边走
					q.push(Strep(s.x-1,s,steps+1));//把节点
					visited[s.x-1]=1;
				}
				//跳跃走法
				if(s.x*2<=MAXN&&!VISITED[S.X*2]{
					q.push(Strp(s.x*2,s.steps+1));
					visited[s.x*2]=1;
				}
				q.pop();//队头的元素给扔掉
	
			}
		
	}
	return 0;
}