`
java-mans
  • 浏览: 11339389 次
文章分类
社区版块
存档分类
最新评论

HDU-1548-A strange lift

 
阅读更多

HDU-1548-A strange lift

http://acm.hdu.edu.cn/showproblem.php?pid=1548

基本的BFS,上下两个方向搜索

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
int n;
int visit[205];
int num[205];
struct node
{
	int x;
	int step;
};
int go(int x)
{
	if(1<=x&&x<=n)
	return 1;
	return 0;
}
int bfs(int a,int b)
{
	queue<node>q;
	node st,ed;
	int t;
	st.x=a;
	st.step=0;
	q.push(st);
	memset(visit,0,sizeof(visit));
	visit[st.x]=1;
	while(!q.empty())
	{
		st=q.front();
		q.pop();
		if(st.x==b)
		return st.step;
		t=st.x+num[st.x];
		if(go(t)&&!visit[t])
		{
			visit[t]=1;
			ed.x=t;
			ed.step=st.step+1;
			q.push(ed);
		}
		t=st.x-num[st.x];
		if(go(t)&&!visit[t])
		{
			visit[t]=1;
			ed.x=t;
			ed.step=st.step+1;
			q.push(ed);
		}
	}
	return -1;
}
int main()
{
	int i,ans;
	int a,b;
	while(scanf("%d",&n),n)
	{
		scanf("%d%d",&a,&b);
        for(i=1;i<=n;i++)
		scanf("%d",&num[i]);
		if(a==b)
		{
			printf("0\n");
			continue;
		}
		ans=bfs(a,b);
		printf("%d\n",ans);
	}
	return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics