ZOJ Problem Set - 3890
One day Leon finds a very classic game called Wumpus.The game is as follow.
For each step, there are six possible movements including going forward, turning left, turning right, shooting, grabbing the gold, and climbing out of the cave. If the agent steps into a square containing a pit or Wumpus, he will die. When the agent shoots, the Wumpus in front of him will die. The goal of the agent is to grab all of the gold and return to the starting position and climb out(it's OK if any Wumpus is still living).When a brick of gold is grabbed successfully, you will gain 1000 points. For each step you take, you will lose 10 points.
Your job is to help him compute the highest point he can possibly get.
For the purpose of simplification, we suppose that there is only one brick of gold and the agent cannot shoot the Wumpus.
There are multiple cases. The first line will contain one integer k that indicates the number of cases.
The output contains one line with one integer, which is the highest point Leon could possibly get. If he cannot finish the game, print "-1".
2 3 1 1 1 2 2 0 3 2 2 -1 -1 -1 3 1 1 1 3 2 2 -1 -1 -1
For the sample 1, the following steps are taken:
Author: JIANG, Kairong
Source: ZOJ Monthly, July 2015