首页 > 搜索 > BFS搜索 > hdu 2425 Hiking Trip-BFS-[解题报告]C++
2014
01-26

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

Hiking Trip

问题描述 :

Hiking in the mountains is seldom an easy task for most people, as it is extremely easy to get lost during the trip. Recently Green has decided to go on a hiking trip. Unfortunately, half way through the trip, he gets extremely tired and so needs to find the path that will bring him to the destination with the least amount of time. Can you help him?
You’ve obtained the area Green’s in as an R * C map. Each grid in the map can be one of the four types: tree, sand, path, and stone. All grids not containing stone are passable, and each time, when Green enters a grid of type X (where X can be tree, sand or path), he will spend time T(X). Furthermore, each time Green can only move up, down, left, or right, provided that the adjacent grid in that direction exists.
Given Green’s current position and his destination, please determine the best path for him.

输入:

There are multiple test cases in the input file. Each test case starts with two integers R, C (2 <= R <= 20, 2 <= C <= 20), the number of rows / columns describing the area. The next line contains three integers, VP, VS, VT (1 <= VP <= 100, 1 <= VS <= 100, 1 <= VT <= 100), denoting the amount of time it requires to walk through the three types of area (path, sand, or tree). The following R lines describe the area. Each of the R lines contains exactly C characters, each character being one of the following: ‘T’, ‘.’, ‘#’, [email protected], corresponding to grids of type tree, sand, path and stone. The final line contains four integers, SR, SC, TR, TC, (0 <= SR < R, 0 <= SC < C, 0 <= TR < R, 0 <= TC < C), representing your current position and your destination. It is guaranteed that Green’s current position is reachable � that is to say, it won’t be a ‘@’ square.
There is a blank line after each test case. Input ends with End-of-File.

输出:

There are multiple test cases in the input file. Each test case starts with two integers R, C (2 <= R <= 20, 2 <= C <= 20), the number of rows / columns describing the area. The next line contains three integers, VP, VS, VT (1 <= VP <= 100, 1 <= VS <= 100, 1 <= VT <= 100), denoting the amount of time it requires to walk through the three types of area (path, sand, or tree). The following R lines describe the area. Each of the R lines contains exactly C characters, each character being one of the following: ‘T’, ‘.’, ‘#’, [email protected], corresponding to grids of type tree, sand, path and stone. The final line contains four integers, SR, SC, TR, TC, (0 <= SR < R, 0 <= SC < C, 0 <= TR < R, 0 <= TC < C), representing your current position and your destination. It is guaranteed that Green’s current position is reachable � that is to say, it won’t be a ‘@’ square.
There is a blank line after each test case. Input ends with End-of-File.

样例输入:

4 6
1 2 10
T...TT
TTT###
TT.@#T
..###@
0 1 3 0

4 6
1 2 2
T...TT
TTT###
TT.@#T
..###@
0 1 3 0

2 2
5 1 3
T@
@.
0 0 1 1

样例输出:

Case 1: 14
Case 2: 8
Case 3: -1

题意很明了,就是找起点到终点的最短用时,但是因为每种不同的地带,用时不同,那么这里可以用到优先队列,来处理总共用时,我们每次总是把用时最短的坐标点出队,访问四周,那么,就总能选择用时最短的去走,直到达到目的地:

上马:

0MS 244K

#include<cstdio>
#include<queue>
using namespace std;
#define MAX 22

struct node
{
	int x,y,time;//坐标,以及起点到此点的用时
	bool operator <(const node &N)const//用优先队列,按用时从小到大排序
	{
		return N.time<time;
	}
}st;//开始点

int R,C;//行列
int endx,endy;//目标的坐标
char map[MAX][MAX];
int T[3];//对于三种不同地带的用时

void Input()
{
	int i;
	scanf("%d%d%d",&T[0],&T[1],&T[2]);
	for(i=0;i<R;i++,getchar())
		scanf("%s",map[i]);
	scanf("%d%d%d%d",&st.x,&st.y,&endx,&endy);
	st.time=0;
}

int vis[4][2]={{-1,0},{1,0},{0,1},{0,-1}};

int bfs()
{
	priority_queue<node>q;
	map[st.x][st.y]='@';//走过了的地方我们就标记为石头,不再走
	q.push(st);

	while(!q.empty())
	{
		node pre=q.top();q.pop();
		if(pre.x==endx && pre.y==endy)
		{
			return pre.time;
		}
		for(int i=0;i<4;i++)
		{
			node p;
			p.x=pre.x+vis[i][0];
			p.y=pre.y+vis[i][1];
			p.time=pre.time;
			if(p.x>=0 && p.y >= 0 && p.x < R && p.y < C && map[p.x][p.y]!='@')//对于地图中不是石头的地方访问
			{
				if(map[p.x][p.y]=='T')p.time+=T[2];//这里看看是哪一种地带,
				else if(map[p.x][p.y]=='.')p.time+=T[1];
				else if(map[p.x][p.y]=='#')p.time+=T[0];
				map[p.x][p.y]='@';
				q.push(p);
			}
		}
	}
	return -1;//走不到返回-1
}

int main()
{
	int cas=1;
	while(~scanf("%d%d",&R,&C))
	{
		Input();
		printf("Case %d: %d\n",cas++,bfs());
	}
	return 0;
}

个人愚昧观点,欢迎指正和交流

解题转自:http://blog.csdn.net/zyy173533832/article/details/10830081


  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  4. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }