Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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 x 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 the moment 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 reach 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.

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:

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

Input 

The input consists of several test cases. Each test case begins with a line containing two integers W and H ( 1W, 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.

Output 

For each test case, if it is possible for Scared John to travel back in time indefinitely, output `Never'. Otherwise, print the minimum time in seconds that it takes him to cross the graveyard from the entrance to the exit if it is reachable, and `Impossible' if not.

Sample Input 

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

Sample Output 

Impossible
4
Never

---

題目描述：

這膽小鬼要經過墓園，其中墓碑是無法經過得地方。

其中有幾處地方有墓穴，會掉入異次元跑到另一個地方，中間會存在不確定的時間流逝。

由於這個膽小鬼想要盡可能走出墓園，因此它會盡可能走墓穴，有可能會無限輪迴於這個墓穴傳遞。

一旦經過墓穴，一定會被吸進去！

膽小鬼只能上下左右走，每走一步消耗 1 秒。

問 1. 困在墓穴(不斷地回朔至過去) 2. 根本離不開 3. 最小消耗

題目解法：

使用 SPFA 找負環。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <deque>
using namespace std;
int g[35][35];
int hole[35][35][3];
int W, H, G, E;
int spfa(int &negcycle) {
	deque<int> X, Y;
	int x, y, tx, ty;
	int i, j, k;
	int dx[] = {0,0,1,-1};
	int dy[] = {1,-1,0,0};
	int inq[35][35] = {}, inqc[35][35] = {};
	int dist[35][35];
	int node = 0;
	for(i = 0; i < W; i++)
		for(j = 0; j < H; j++)
			node += g[i][j] == 0;
	memset(dist, 63, sizeof(dist));
	X.push_front(0), Y.push_front(0);
	dist[0][0] = 0, inqc[0][0]++;
	while(!X.empty()) {
		x = X.front(), X.pop_front();
		y = Y.front(), Y.pop_front();
		inq[x][y] = 0;
		if(x == W-1 && y == H-1)
			continue;
		if(hole[x][y][0] != -1) {//haunted hole
			tx = hole[x][y][0], ty = hole[x][y][1];
			if(dist[tx][ty] > dist[x][y] + hole[x][y][2]) {
				dist[tx][ty] = dist[x][y] + hole[x][y][2];
				if(inq[tx][ty] == 0)  {
					if(!X.empty() && dist[X.front()][Y.front()] > dist[tx][ty])
						X.push_front(tx), Y.push_front(ty);
					else
						X.push_back(tx), Y.push_back(ty);
					inq[tx][ty] = 1;
					if(++inqc[tx][ty] > node) {
						negcycle = 1;
						return 0; // negative cycle
					}
				}
			}
			continue;//important
		}
		for(i = 0; i < 4; i++) {
			tx = x+dx[i], ty = y+dy[i];
			if(tx < 0 || ty < 0 || tx >= W || ty >= H)
				continue;
			if(g[tx][ty])	continue;//gravestone
			if(dist[tx][ty] > dist[x][y]+1) {
				dist[tx][ty] = dist[x][y]+1;
				if(inq[tx][ty] == 0)  {
					if(!X.empty() && dist[X.front()][Y.front()] > dist[tx][ty])
						X.push_front(tx), Y.push_front(ty);
					else
						X.push_back(tx), Y.push_back(ty);
					inq[tx][ty] = 1;
					if(++inqc[tx][ty] > node) {
						negcycle = 1;
						return 0; // negative cycle
					}
				}
			}
		}
	}
	return dist[W-1][H-1];
}
int main() {
	int i, j, k, x, y;
	int sx, sy, ex, ey, t;
	while(scanf("%d %d", &W, &H) == 2 && W+H) {
		memset(g, 0, sizeof(g));
		memset(hole, -1, sizeof(hole));
		scanf("%d", &G);
		for(i = 0; i < G; i++) {
			scanf("%d %d", &x, &y);
			g[x][y] = 1;
		}
		scanf("%d", &E);
		for(i = 0; i < E; i++) {
			scanf("%d %d %d %d %d", &sx, &sy, &ex, &ey, &t);
			hole[sx][sy][0] = ex;
			hole[sx][sy][1] = ey;
			hole[sx][sy][2] = t;
		}
		int negcycle = 0;
		int ret = spfa(negcycle);
		if(negcycle)
			puts("Never");
		else if(ret == 0x3f3f3f3f)
			puts("Impossible");
		else
			printf("%d\n", ret);
	}
	return 0;
}