GitBook

这里写图片描述 这里写图片描述

这里用了广搜 也就是每次 对m+1,m-1,m*2判断 遇到还没到过的点就加入搜索队列 直到目标点有了记录

需要注意的是给搜索加入越界判断 防止有数组超限等情况

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int n,e;
int MAX=100200;
int dis[100200];
void bfs(int m) {
	queue<int>q;
	q.push(m);
	while(q.front()!=e) {
		int t=q.front();
		if(t+1<MAX&&!dis[t+1]) {
			dis[t+1]=dis[t]+1;
			q.push(t+1);
		}
		if(t-1>=0&&!dis[t-1]) {
			dis[t-1]=dis[t]+1;
			q.push(t-1);
		}
		if(t*2<MAX&&!dis[t*2]) {
			dis[t*2]=dis[t]+1;
			q.push(t*2);
		}
		if(dis[e])
			break;
		q.pop();
	}
	return ;
}
int main() {
	while(scanf("%d %d",&n,&e)!=EOF) {
		memset(dis,0,sizeof(dis));
		bfs(n);
		printf("%d\n",dis[e]);
	}
	return 0;
}

题目地址:【杭电】[2717]Catch That Cow