3439 bfs a搜索.txt

ACM资料大集合

#include <iostream>
#include <queue>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <iterator>
#include <algorithm>
using namespace std;

//3439 BFS A*搜索
#define N 1100
#define INF 1500
#define PH push_heap
#define OH pop_heap
#define OB pop_back
#define PB push_back

typedef struct oppoint
{
	double x;
	double y;
	int old;
	int left;
	int right;
}oppoint;

typedef struct opa
{
	int value;
	double score;//路程分数
}opa;

oppoint point[N];
int q[N];

int cmp1(const void *a,const void *b)
{
	if(((oppoint *)a)->x==((oppoint *)b)->x) return (int)(((oppoint *)a)->y-((oppoint *)b)->y);
	else return (int)(((oppoint *)a)->x-((oppoint *)b)->x);
}

bool cmp(oppoint a,oppoint b)
{
	if(a.x==b.x) return a.y<b.y;
	else return a.x<b.x;
}

double gscore(int now,int end,double pas)
{
	return sqrt((point[now].x-point[end].x)*(point[now].x-point[end].x)+(point[now].y-point[end].y)*(point[now].y-point[end].y))+pas;
}

bool gscmp(opa a,opa b)
{
	return a.score>b.score;
}
void build(int num,double l1,double l2)
{
	double ll=l1+l2;
	int i,j,k,t;
	i=1;j=1;
	for(k=1;k<=num;k++)
	{
		while(point[j].x-point[k].x<=ll && j<num) j++;
		while(point[k].x-point[i].x>ll && i<num) i++;
		point[k].left=i;
		point[k].right=j;
	}
}

void SPFA(int start,int end,int num,double ll)
{
	int s,t,now,flag=0,i;
	int vis[N],len[N],q[N];
	opa temp;
	vector <opa> hh;
	memset(len,INF,sizeof(len));
	memset(vis,0,sizeof(vis));
	temp.value=start;
	temp.score=gscore(start,end,0);
	hh.clear();
	hh.PB(temp);
	PH(hh.begin(),hh.end(),gscmp);
	vis[start]=1;
	len[start]=0;
	while(!hh.empty())
	{
		now=(hh.front()).value;
		if(now==end) {flag=1;break;}
		OH(hh.begin(),hh.end(),gscmp);
		hh.OB();
		for(i=point[now].left;i<=point[now].right;i++)
		{
			if(vis[i]==0 && (point[i].x-point[now].x)*(point[i].x-point[now].x)+(point[i].y-point[now].y)*(point[i].y-point[now].y)<=ll*ll)
			{
				temp.value=i;
				len[i]=len[now]+1;
				vis[i]=1;
				temp.score=gscore(i,end,len[i]*ll);
				hh.PB(temp);
				PH(hh.begin(),hh.end(),gscmp);		
			}
		}
	}
	
/*	
	memset(q,0,sizeof(q));
	memset(vis,0,sizeof(vis));
	s=t=0;
	q[t++]=start;
	memset(len,INF,sizeof(len));
	vis[start]=1;
	len[start]=0;
	while(s<t)
	{
		now=q[s++];
		if(now==end) {flag=1;break;}
		for(i=point[now].left;i<=point[now].right;i++)
		{
			if((point[i].x-point[now].x)*(point[i].x-point[now].x)+(point[i].y-point[now].y)*(point[i].y-point[now].y)<=ll*ll)
			{
				if(vis[i]==0)
				{
					len[i]=len[now]+1;
					q[t++]=i;
					vis[i]=1;
				}
			}
		}
	}
*/	
   	if(0==flag) printf("Impossible\n");
	else printf("%d\n",len[end]);
}

int main()
{
	int cnum,i,j,num,start,end,ts,te;
	double l1,l2;
	scanf("%d",&cnum);
	for(i=1;i<=cnum;i++)
	{
//		cin>>num>>start>>end>>l1>>l2;
		scanf("%d %d %d %lf %lf",&num,&start,&end,&l1,&l2);
		for(j=1;j<=num;j++)
		{
			scanf("%lf %lf",&point[j].x,&point[j].y);
			point[j].old=j;
		}
//		sort(point+1,point+num+1,cmp);
		qsort(point+1,num,sizeof(point[1]),cmp1);
		for(j=1;j<=num;j++)
		{
			if(point[j].old==start) ts=j;
			if(point[j].old==end) te=j;
		}
		start=ts;
		end=te;
		build(num,l1,l2);
		SPFA(start,end,num,l1+l2);
	}
	return 0;
}