UVa 10557

XYZZY

from Volume 2. Data Structures :: Graphs

Description

玩一个游戏。一共有 n 个房间，每个房间都通向其他几个房间。你带着100点能量进入第一个房间，每进入一个房间，都会根据这个房间的属性增加或减少能量。一旦能量降为0或者低于0，你就 game over 。只有到达最后一个房间，你才能算胜利。输入房间的数量和每个房间的情况，包括每个房间通往哪几个房间。输出是否能取得胜利。注意：房间的路是单向通行的，但是你可以不停地到达某个房间或绕圈子，使得你具有更多的能量。

Solution

注意这道题将会有回路。通过回路，既可以使得你的能量无限大，但是你也可能在回路中出不来。所以如果用搜索去做这道题，如何处理回路的情况是关键。搜索的话有两种做法，DFS 和 BFS。

1. DFS：需要二重的 DFS，第一重就是常规地去走每一个能够走的房间。而第二重，就是在第一重 DFS 时，碰到走过的房间，如果此时能量大于上次来的时候的能量，就说明你可以利用这个回路来使自己的能量无穷大，此时，只要开启第二种 DFS ，看看你所在的房间，能否到达目的房间（路上无视计算能量的影响），即可。如果此时能量小于或等于上次来的时候的能量，说明你没有必要走这个回路，退出搜索即可。
2. BFS：常规的 BFS ，不过在到底某个房间时，需要记录你到达这个房间的能量。下次来到这个房间的时候，如果能量更低就不必将此时的状态入栈，如果能量更高就更新到达这个房间的能量值。在搜索的时候，发现能量发生异常（能量值已经很大了，还没有退出队列），就说明这时候已经陷入环中无法自拔了，退出循环，判定游戏失败即可。