ZOJ Problem Set - 3611
On the way to the Dragon's Castle, there is an Ice Valley. Now Lott wants to pass through the Ice Valley. While in the Ice Valley, there was a lot of treasure, and the treasure can be helpful to Lott, so Lott wants to get as many treasure as he can.
Now, Lott has reached the Ice Valley, and he finds that the Ice Valley is made up of n*m blocks. And on the blocks there are different signs. Lott has been told by friendly NPC that the meaning of each signs:
The meaning of each signs:
Now, Lott starts at the entrance of the valley x1, y1. He wants to get to the exit at the position of x2, y2. And at the same time, Lott wants to get the most treasure he can. The entrance and the exit are both signed nothing. The entrance and the exit can be the same positions.
Now, we assume that each movement from one block to another costs 1 second and each opening of one box spends 2 seconds, and we want to know the minimum time Lott uses to pass through the valley with the most treasure.
There are multiple cases.
In each cases, the first line contains two integers n , m. (1<=n<=500 , 1<=m<=500)
Then n lines with m characters describing the valley. And '0' represents nothing; 'L','U','D','R' represents arrow with the direction of left, up, down, right; 'W' represents a wall; '$' represents a box with treasure; '#' represents the trap hole.
Then the last line with four integer x1, y1, x2, y2. (1<=x1<=500 , 1<=y1<=500 , 1<=x2<=500 , 1<=y2<=500)
Of each case, output one line with one integer representing the minimum time Lott will use, if he cannot pass through the valley, output -1.
5 5 DL0R$ DWDWD DL$LL D#DWU RURR0 1 3 5 5 5 5 0RRRD UW$#D UD0UD U#$WD ULLLL 1 1 3 3
Author: XIONG, Siyuan
Contest: ZOJ Monthly, June 2012