首页 > ACM题库 > HDU-杭电 > HDU 4076-Haunted Graveyard-最短路径-[解题报告]HOJ
2015
04-16

HDU 4076-Haunted Graveyard-最短路径-[解题报告]HOJ

Haunted Graveyard

问题描述 :

Tonight is Halloween and Scared John and his friends have decided to do something fun to celebrate the occasion: crossing the graveyard. Although Scared John does not find this fun at all, he finally agreed to join them in their adventure. Once at the entrance, the friends have begun to cross the graveyard one by one, and now it is the time for Scared John. He still remembers the tales his grandmother told him when he was a child. She told him that, on Halloween night, "haunted holes" appear in the graveyard. These are not usual holes, but they transport people who fall inside to some point in the graveyard, possibly far away. But the scariest feature of these holes is that they allow one to travel in time as well as in space; i.e., if you fall inside a "haunted hole", you appear somewhere in the graveyard a certain time before (or after) you entered the hole, in a parallel universe otherwise identical to ours.
The graveyard is organized as a grid of W*H cells, with the entrance in the cell at position (0, 0) and the exit at (W-1, H-1). Despite the darkness, Scared John can always recognize the exit, and he will leave as soon as he reaches it, determined never to set foot anywhere in the graveyard again. On his way to the exit, he can walk from one cell to an adjacent one, and he can only head to the North, East, South or West. In each cell there can be either one gravestone, one "haunted hole", or grass:

If the cell contains a gravestone, you cannot walk over it, because gravestones are too high to climb.
If the cell contains a "haunted hole" and you walk over it, you will appear somewhere in the graveyard at a possibly different moment in time. The time difference depends on the particular "haunted hole" you fell into, and can be positive, negative or zero.
Otherwise, the cell has only grass, and you can walk freely over it.

He is terrified, so he wants to cross the graveyard as quickly as possible. And that is the reason why he has phoned you, a renowned programmer. He wants you to write a program that, given the description of the graveyard, computes the minimum time needed to go from the entrance to the exit. Scared John accepts using "haunted holes" if they permit him to cross the graveyard quicker, but he is frightened to death of the possibility of getting lost and being able to travel back in time indefinitely using the holes, so your program must report these situations.

Genetics

Figure 3 illustrates a possible graveyard (the second test case from the sample input). In this case there are two gravestones in cells (2, 1) and (3, 1), and a "haunted hole" from cell (3, 0) to cell (2, 2) with a difference in time of 0 seconds. The minimum time to cross the graveyard is 4 seconds, corresponding to the path:

Genetics

If you do not use the "haunted hole", you need at least 5 seconds.

输入:

The input consists of several test cases. Each test case begins with a line containing two integers W and H (1 <= W, H <= 30). These integers represent the width W and height H of the graveyard. The next line contains an integer G (G >= 0), the number of gravestones in the graveyard, and is followed by G lines containing the positions of the gravestones. Each position is given by two integers X and Y (0 <= X < W and 0 <= Y < H).
The next line contains an integer E (E >= 0), the number of "haunted holes", and is followed by E lines. Each of these contains five integers X1, Y1, X2, Y2, T. (X1, Y1) is the position of the "haunted hole" (0 <= X1 < W and 0 <= Y1 < H). (X2, Y2) is the destination of the "haunted hole" (0 <= X2 < W and 0 <= Y2 < H). Note that the origin and the destination of a "haunted hole" can be identical. T (-10 000 <= T <= 10 000) is the difference in seconds between the moment somebody enters the "haunted hole" and the moment he appears in the destination position; a positive number indicates that he reaches the destination after entering the hole. You can safely assume that there are no two "haunted holes" with the same origin, and the destination cell of a "haunted hole" does not contain a gravestone. Furthermore, there are neither gravestones nor "haunted holes" at positions (0,0) and (W-1,H-1). The input will finish with a line containing 0 0, which should not be processed.

输出:

The input consists of several test cases. Each test case begins with a line containing two integers W and H (1 <= W, H <= 30). These integers represent the width W and height H of the graveyard. The next line contains an integer G (G >= 0), the number of gravestones in the graveyard, and is followed by G lines containing the positions of the gravestones. Each position is given by two integers X and Y (0 <= X < W and 0 <= Y < H).
The next line contains an integer E (E >= 0), the number of "haunted holes", and is followed by E lines. Each of these contains five integers X1, Y1, X2, Y2, T. (X1, Y1) is the position of the "haunted hole" (0 <= X1 < W and 0 <= Y1 < H). (X2, Y2) is the destination of the "haunted hole" (0 <= X2 < W and 0 <= Y2 < H). Note that the origin and the destination of a "haunted hole" can be identical. T (-10 000 <= T <= 10 000) is the difference in seconds between the moment somebody enters the "haunted hole" and the moment he appears in the destination position; a positive number indicates that he reaches the destination after entering the hole. You can safely assume that there are no two "haunted holes" with the same origin, and the destination cell of a "haunted hole" does not contain a gravestone. Furthermore, there are neither gravestones nor "haunted holes" at positions (0,0) and (W-1,H-1). The input will finish with a line containing 0 0, which should not be processed.

样例输入:

3 3
2
2 1
1 2
0
4 3
2
2 1
3 1
1
3 0 2 2 0
4 2
0
1
2 0 1 0 -3
0 0

样例输出:

Impossible
4
Never

/*
hdu 4076 Haunted Graveyard - spfa(负权回路)
题意:有n*m个点,每一点可以向四个方向走,有些点是墓地不能走,有些点是山洞,当你走到该点时会传送到另外一点,所花费的时间有可能是个正数也可能是个负数
也可能是0。起点是(0,0),目的地是(n-1,m-1),题目保证起点和终点不会是墓地也不会是山洞。如果有可能永远都到达不了终点也就是该图存在负权回路,输出Never;
否则输出需最少的花费时间或者Impossible;
思路:存在负权,显然要用spfa。当对某一个点的松弛次数超时该图的顶点数n*m时就表示存在负权回路。
但是有一点需要注意:判断负权回路的时候不能把终点算在内,因为当第一次走到终点的时候就走出去了,终点不会对他的后继点进行松弛。
*/
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define inf 0xfffffff
const int N=35;
int map[N][N],xx[N][N],yy[N][N],tt[N][N],dist[N][N],vis[N][N],cnt[N][N];
int dir[4][2]= { {0,1},{0,-1},{1,0},{-1,0} };
int W,H,flag;
struct node
{
    int x,y;
};
void spfa()
{
    int i,j,ans;
    for(i=0; i<W; ++i)
    {
        for(j=0; j<H; ++j)
        {
            dist[i][j]=inf;
        }
    }
    dist[0][0]=0;
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    queue<node> q;
    node cur,next;
    cur.x=0;
    cur.y=0;
    next.x=next.y=0;
    q.push(cur);
    vis[0][0]=1;
    cnt[0][0]++;
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
        vis[cur.x][cur.y]=0;//是否在队列内
        if(cnt[cur.x][cur.y]>W*H)
        {
            flag=1;
            return;
        }
        if(cur.x==W-1&&cur.y==H-1)continue;
        if(xx[cur.x][cur.y]!=-1)
        {
            next.x=xx[cur.x][cur.y];
            next.y=yy[cur.x][cur.y];
            ans=dist[cur.x][cur.y]+tt[cur.x][cur.y];
            if(dist[next.x][next.y]>ans)
            {
                dist[next.x][next.y]=ans;
                if(vis[next.x][next.y]==0)
                {
                    vis[next.x][next.y]=1;
                    cnt[next.x][next.y]++;
                    q.push(next);
                }
            }
            continue;
        }

        for(i=0; i<4; ++i)
        {
            next.x=cur.x+dir[i][0];
            next.y=cur.y+dir[i][1];
            ans=dist[cur.x][cur.y]+1;
            if(next.x<0 || next.y<0 || next.x>=W || next.y>=H || map[next.x][next.y]==1) continue;
            if(dist[next.x][next.y]>ans)
            {
                dist[next.x][next.y]=ans;
                if(vis[next.x][next.y]==0)
                {
                    vis[next.x][next.y]=1;
                    cnt[next.x][next.y]++;
                    q.push(next);
                }
            }
        }
    }
}
int main()
{
    int numofmu,numofdong,i,tempa,tempb;
    while(cin>>W>>H,W+H)
    {
        flag=0;
        memset(map,0,sizeof(map));
        memset(xx,-1,sizeof(xx));
        cin>>numofmu;
        for(i=1; i<=numofmu; ++i)
        {
            cin>>tempa>>tempb;
            map[tempa][tempb]=1;
        }
        cin>>numofdong;
        for(i=1; i<=numofdong; ++i)
        {
            cin>>tempa>>tempb;
            cin>>xx[tempa][tempb]>>yy[tempa][tempb]>>tt[tempa][tempb];
        }
        spfa();
        if(flag==1) cout<<"Never"<<endl;
        else if(dist[W-1][H-1]==inf) cout<<"Impossible"<<endl;
        else cout<<dist[W-1][H-1]<<endl;
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/qq172108805/article/details/8932060


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

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。