飞跃原野

飞跃原野

时间: 5ms        内存:64M

描述:

勇敢的法里奥出色的完成了任务之后,正在迅速地向自己的基地撤退。但由于后面有着一大群追兵,所以法里奥要尽快地返回基地,否则就会被敌人逮住。
终于,法里奥来到了最后的一站:泰拉希尔原野,穿过这里就可以回到基地了。然而,敌人依然紧追不舍。不过,泰拉希尔的地理条件对法里奥十分有利,众多的湖泊随处分布。敌人需要绕道而行,但法里奥还是决定找一条能尽快回到基地的路。
假设泰拉希尔原野是一个m*n的矩阵,它有两种地形,P表示平,L表示湖泊,法里奥只能停留在平地上。他目前的位置在左上角(1,1)处,而目的地为右下角的(m,n)。法里奥可以向前后左右4个方向移动或飞行,每移动1格需要1单位时间。而飞行的时间主要花费在变形上,飞行本身时间消耗很短,所以无论一次飞行多远的距离,都只需要1单位时间。飞行的途中不能变向,并且一次飞行最终必须要降落到平地上。当然,由于受到能量的限制,法里奥不能无限制飞行,他总共最多可以飞行的距离为D。在知道了以上的信息之后,请你帮助法里奥计算一下,他最快到达基地所需要的时间。

输入:

第一行是3个整数,m(1≤m≤100),n(1≤n≤100),D(1≤D≤100)。表示原野是m*n的矩阵,法里奥最多只能飞行距离为D。接下来的m行每行有n个字符,相互之间没有空格。P表示当前位置是平地,L则表示湖泊。假定(1,1)和(m,n)一定是平地。

输出:

一个整数,表示法里奥到达基地需要的最短时间。如果无法到达基地,则输出impossible。

示例输入:

4 4 2
PLLP
PPLP
PPPP
PLLP

示例输出:

5

提示:

参考答案(内存最优[1488]):

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int dir[4][2]={1,0,0,1,-1,0,0,-1};//方向
int m,n,D;
int visited[101][101];//记录是否到达过该坐标
char map[101][101];
int DD[101][101];//记录到达该坐标最小步数
 //即,地图每个点都要记录到达该点是用过的最小飞翔能量D,如果后来花更少的能量
//到达该点,需更新该点的已用最小能量。 好题!
struct pos
{
	int x,y;//坐标
	int step;//步数
	int D;//记录走到当前位置用过的飞翔时间
};
bool cango(int x,int y,int s)//判断越界及visited
{
	if(x<0||x>=m||y<0||y>=n) return false;
	if(visited[x][y]&&s>DD[x][y]) return false;//该判断及为与普通广搜不同之处,
	//因为飞翔的限制,当一个点被访问过后,如果之后又访问该点且用过的飞翔步数D更少,则需要更新该店的最小D值,然后入队列。
	return true;
}
int bfs()
{
	memset(visited,0,sizeof(visited));
	memset(DD,0,sizeof(DD));
	queue<pos> que;
	pos p;
	p.x=0;
	p.y=0;
	p.step=0;
	visited[0][0]=1;
	DD[0][0]=0;
	p.D=0;
	que.push(p);
	while(!que.empty())
	{
		pos cur=que.front();
		que.pop();
		for(int i=0;i<4;i++)
		{
			pos next;
			next.x=cur.x+dir[i][0];
			next.y=cur.y+dir[i][1];
			next.D=cur.D;
			if(cango(next.x,next.y,cur.D))
			{
				next.step=cur.step+1;
				DD[next.x][next.y]=next.D;
				if(next.x==m-1&&next.y==n-1) return next.step;

				if(map[next.x][next.y]=='P'){//下一步为平地
					visited[next.x][next.y]=1;
					que.push(next);
				}
				else{                         //下一步为湖泊
					next.D++;
					for(int j=1;;j++)
					{
						next.x+=dir[i][0];
						next.y+=dir[i][1];
						next.D++;
						if(next.D>D) break;
						if(!cango(next.x,next.y,cur.D)) break;
						if(next.x==m-1&&next.y==n-1) return next.step;
						if(map[next.x][next.y]=='L') continue;
						else {
							que.push(next);
							visited[next.x][next.y]=1;
							DD[next.x][next.y]=next.D;
							break;
						}
					}
				}
			}
		}
	}
	return -1;
}
int main()
{
	scanf("%d%d%d",&m,&n,&D);
	getchar();
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
			scanf("%c",&map[i][j]);
		getchar();
	}
	int res=0;
	res=bfs();
		printf("%d\n",res);
		return 0;
}

参考答案(时间最优[0]):

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int dir[4][2]={1,0,0,1,-1,0,0,-1};//方向
int m,n,D;
int visited[101][101];//记录是否到达过该坐标
char map[101][101];
int DD[101][101];//记录到达该坐标最小步数
 //即,地图每个点都要记录到达该点是用过的最小飞翔能量D,如果后来花更少的能量
//到达该点,需更新该点的已用最小能量。 好题!
struct pos
{
	int x,y;//坐标
	int step;//步数
	int D;//记录走到当前位置用过的飞翔时间
};
bool cango(int x,int y,int s)//判断越界及visited
{
	if(x<0||x>=m||y<0||y>=n) return false;
	if(visited[x][y]&&s>DD[x][y]) return false;//该判断及为与普通广搜不同之处,
	//因为飞翔的限制,当一个点被访问过后,如果之后又访问该点且用过的飞翔步数D更少,则需要更新该店的最小D值,然后入队列。
	return true;
}
int bfs()
{
	memset(visited,0,sizeof(visited));
	memset(DD,0,sizeof(DD));
	queue<pos> que;
	pos p;
	p.x=0;
	p.y=0;
	p.step=0;
	visited[0][0]=1;
	DD[0][0]=0;
	p.D=0;
	que.push(p);
	while(!que.empty())
	{
		pos cur=que.front();
		que.pop();
		for(int i=0;i<4;i++)
		{
			pos next;
			next.x=cur.x+dir[i][0];
			next.y=cur.y+dir[i][1];
			next.D=cur.D;
			if(cango(next.x,next.y,cur.D))
			{
				next.step=cur.step+1;
				DD[next.x][next.y]=next.D;
				if(next.x==m-1&&next.y==n-1) return next.step;

				if(map[next.x][next.y]=='P'){//下一步为平地
					visited[next.x][next.y]=1;
					que.push(next);
				}
				else{                         //下一步为湖泊
					next.D++;
					for(int j=1;;j++)
					{
						next.x+=dir[i][0];
						next.y+=dir[i][1];
						next.D++;
						if(next.D>D) break;
						if(!cango(next.x,next.y,cur.D)) break;
						if(next.x==m-1&&next.y==n-1) return next.step;
						if(map[next.x][next.y]=='L') continue;
						else {
							que.push(next);
							visited[next.x][next.y]=1;
							DD[next.x][next.y]=next.D;
							break;
						}
					}
				}
			}
		}
	}
	return -1;
}
int main()
{
	scanf("%d%d%d",&m,&n,&D);
	getchar();
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
			scanf("%c",&map[i][j]);
		getchar();
	}
	int res=0;
	res=bfs();
		printf("%d\n",res);
		return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注