首页 > 搜索 > BFS搜索 > hdu 2383 Hiking-BFS-[解题报告]C++
2014
01-05

hdu 2383 Hiking-BFS-[解题报告]C++

Hiking

问题描述 :

You have gone on a hiking trip, but now you are getting tired and would like to return home. As a precaution, you always take your mobile phone with you, so you can call for help in case of an emergency. However, it only works as long as you stay in range of (one of) the phone towers in the area. Fortunately, you know precisely where you are and where you are going, and you brought a map of the area showing the locations of the mobile phone towers. You want to take the shortest route home, while staying in range of at least one of those towers.

输入:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with two integers d (1 <= d <= 1 000) and t (1 <= t <= 100): the maximum distance to the nearest tower and the number of towers on the map, respectively.

One line containing the starting location.

One line containing the goal location.

t lines each containing the location of a tower.

All locations consist of two space-separated integer coordinates x and y (1 <= x, y <= 1 000).

All locations in the input for a single test case will be distinct. The starting locating will not be more than d units away from the nearest tower.

输出:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with two integers d (1 <= d <= 1 000) and t (1 <= t <= 100): the maximum distance to the nearest tower and the number of towers on the map, respectively.

One line containing the starting location.

One line containing the goal location.

t lines each containing the location of a tower.

All locations consist of two space-separated integer coordinates x and y (1 <= x, y <= 1 000).

All locations in the input for a single test case will be distinct. The starting locating will not be more than d units away from the nearest tower.

样例输入:

1
2 3
1 1
8 2
2 2
4 4
7 3

样例输出:

7.23224071072994

#include<stdio.h>
#include<string.h>
int map[23][23];
int visit[23][23];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int row,line;
int vp, vs, vt;
int starti,startj,endi,endj;
struct queue
{
	int x,y;
	int va;
};
void Priqueue(int h,int t,struct queue q[])
{
	struct queue b;
	int s = t;
	b = q[t];
	while(b.va<q[--s].va)
		q[s+1] = q[s];
	q[s+1] = b;
}
int BFS()
{
	struct queue queue[19999];
	int tail,head,i;
	memset(visit,0,sizeof(visit));
	tail = head = 0;
	queue[tail].x = starti;
	queue[tail].y = startj;
	queue[tail++].va = 0;
	while(head<tail)
	{
		int X = queue[head].x;
		int Y = queue[head].y;
		int V = queue[head++].va;
		
		if(X==endi && Y==endj)
			return V;
		for(i=0;i<4;i++)
			if(map[X+dir[i][0]][Y+dir[i][1]] && !visit[X+dir[i][0]][Y+dir[i][1]])
			{
				visit[X][Y] = 1;
				queue[tail].x = X+dir[i][0];
				queue[tail].y = Y+dir[i][1];
				queue[tail++].va = V+map[X+dir[i][0]][Y+dir[i][1]];
				Priqueue(head,tail-1,queue);
			}
	}
	return -1;
}
int main()
{
	int i,j,ca=1;
	char ch[30];
	while(scanf("%d%d",&row,&line)!=EOF)
	{
		scanf("%d%d%d",&vp,&vs,&vt);
		memset(map,0,sizeof(map));
		for(i=1;i<=row;i++)
		{
			scanf("%s",ch+1);
			for(j=1;j<=line;j++)
			{
				if(ch[j]=='#')
					map[i][j] = vp;
				else if(ch[j]=='.')
					map[i][j] = vs;
				else if(ch[j]=='T')
					map[i][j] = vt;
			}
		}
		scanf("%d%d%d%d",&starti,&startj,&endi,&endj);
		starti++,startj++,endi++,endj++;
		printf("Case %d: %d\n",ca++,BFS());
		
	}
	return 0;

}
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int map[23][23];
int visit[23][23];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int row,line;
int vp, vs, vt;
int starti,startj,endi,endj;
struct Q
{
	int x,y;
	int va;
	bool operator < (const Q& a)const{
	return va>a.va;
	}
};
int BFS()
{
	struct Q q,qq;
	priority_queue<Q> queue;
	int i;
	memset(visit,0,sizeof(visit));
	while(!queue.empty())
		queue.pop();
	q.x = starti;
	q.y = startj;
	q.va = 0;
	queue.push(q);
	visit[q.x][q.y] = 1;
	while(!queue.empty())
	{
		q = queue.top();
		queue.pop();
		if(q.x==endi && q.y==endj)
			return q.va;
		for(i=0;i<4;i++)
			if(map[q.x+dir[i][0]][q.y+dir[i][1]] && !visit[q.x+dir[i][0]][q.y+dir[i][1]])
			{
				visit[q.x+dir[i][0]][q.y+dir[i][1]] = 1;
				qq.x = q.x+dir[i][0];
				qq.y = q.y+dir[i][1];
				qq.va = q.va+map[q.x+dir[i][0]][q.y+dir[i][1]];
				queue.push(qq);
			}
	}
	return -1;
}
int main()
{
	int i,j,ca=1;
	char ch[30];
	while(scanf("%d%d",&row,&line)!=EOF)
	{
		scanf("%d%d%d",&vp,&vs,&vt);
		memset(map,0,sizeof(map));
		for(i=1;i<=row;i++)
		{
			scanf("%s",ch+1);
			for(j=1;j<=line;j++)
			{
				if(ch[j]=='#')
					map[i][j] = vp;
				else if(ch[j]=='.')
					map[i][j] = vs;
				else if(ch[j]=='T')
					map[i][j] = vt;
			}
		}
		scanf("%d%d%d%d",&starti,&startj,&endi,&endj);
		starti++,startj++,endi++,endj++;
		printf("Case %d: %d\n",ca++,BFS());
		
	}
	return 0;

}

解题转自:http://blog.csdn.net/min_lala/article/details/12257851


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n