catch that cow POJ 3278 搜索

题意

john想要抓到那只牛，John和牛的位置在数轴上表示为n和k，john有三种移动方式：1. 向前移动一个单位，2. 向后移动一个单位，3. 移动到当前位置的二倍处。输出移动的最少次数。

解题思路

使用搜索，准确地说是广搜，要记得到达的位置要进行标记，还有就是减枝。

详情见代码实现。

代码实现

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<map>

using namespace std;

const int inf=0x3f3f3f3f;

const int maxn=1e5+7; //这个是数轴的最大尺度

int n, k, ans=inf;

struct node{

	int x, t;

};

map<int, int> mp; //使用map进行标记

queue<node> q;

void bfs(int x)

{

	mp.clear();

	int tx;

	node h={x, 0};

	q.push(h);

	mp[x]=1; //起点也要进行标记

	while(!q.empty() )

	{

		h=q.front();

		q.pop();

		tx=h.x+1;

		if(mp[tx]==0)

		{

			if(tx == k)

			{

				ans=min(ans, h.t+1);

				return ;

			}

            //只有当john的位置小于牛的位置时，进行加一操作才有意义

			else if(tx < k && tx<maxn)

			{

				node tmp={tx, h.t+1};

				q.push(tmp);

				mp[tx]=1;

			}

		}

		tx=h.x-1;

		if(mp[tx]==0)

		{

			if(tx == k)

			{

				ans=min(ans, h.t+1);

				return ;

			}

			else if(tx >= 0)//减一操作后要判断是不是小于0

			{

				node tmp={tx, h.t+1};

				q.push(tmp);

				mp[tx]=1;

			}

		}

		tx=h.x<<1;

		if(mp[tx]==0)

		{

			if(tx == k)

			{

				ans=min(ans, h.t+1);

				return ;

			}

			else if( h.x < k && tx<maxn) //只有起点小于k时，乘2操作开可以进行

			{

				node tmp={tx, h.t+1};

				q.push(tmp);

				mp[tx]=1;

			}

		}

	}

}

int main()

{

	scanf("%d%d", &n, &k);

	if(n==k)

	ans=0;

	else bfs(n);

	printf("%d\n", ans);

	return 0;

}

巴特西

catch that cow POJ 3278 搜索

catch that cow POJ 3278 搜索

题意

解题思路

代码实现

最新文章

热门文章