2014
01-26

# 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;
}

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

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;
}