【杭电】[2717]Catch That Cow

问题描述

问题分析

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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