bzoj 1646: [Usaco2007 Open]Catch That Cow 抓住那只牛【bfs】

满脑子dp简直魔性

模拟题意bfs转移即可

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

const int N=200005;

int s,t,d[N];

bool v[N];

queue<int>q;

inline void wk(int x,int y)

{

	d[y]=d[x]+1;

	if(!v[y])

	{

		v[y]=1;

		q.push(y);

	}

}

int main()

{

	scanf("%d%d",&s,&t);

	for(int i=0;i<=200000;i++)

		d[i]=1e9;

	v[s]=1,d[s]=0,q.push(s);

	while(!q.empty())

	{

		int u=q.front();

		q.pop();

		v[u]=0;

		if(u*2<=200000&&d[u*2]>d[u]+1)

			wk(u,u*2);

		if(u+1<=200000&&d[u+1]>d[u]+1)

			wk(u,u+1);

		if(u-1>=0&&d[u-1]>d[u]+1)

			wk(u,u-1);

	}

	printf("%d\n",d[t]);

	return 0;

}

巴特西

bzoj 1646: [Usaco2007 Open]Catch That Cow 抓住那只牛【bfs】

最新文章

热门文章