111 - ZOJ Monthly, October 2011 - G
Maybe many one have played or at least heard of The Family Computer(FC). And this problem is mainly about a classical game named "Ice Climber"
In this game, our little Eskimo wants to climb higher and catch the big bird at last. In the climbing, little Eskimo may be faced with many troubles, like enemy or wall.
The game field made up with several floors and floors are seperated by many pieces of bricks. The number of pieces between different floors and different positions are different. There may also be enimies and walls on these bricks. By jumping up Eskimo can decrease the number of pieces on the ceiling of his position or even jump to another floor.
Each time Eskimo can choose on of the following steps:
Each block has several pieces. And only if the number of the pieces of the block is 0 can little Eskimo jump up through it to the next floor. Sometimes Eskimo may clear all the bricks of ceiling of a position where there is an enemy standing on it, in these cases this unlucky enemy will be cleared at once. If on the next floor, above one block there is a wall, then Eskimo can never jump up through this block no matter how much pieces it has even zero. If little Eskimo jumped up to the next floor successfully, for instance through the ith position, he can choose to land on either to the left, the i-1th block or to the right, the i+1th block as you like, but not the ith block itself. And you can never jump over the enemy or the wall or the zero pieces blocks.
And in the whole process, little Eskimo can not land on to the side, that is, he can not land on to the 0th block or the w+1th block. Also, he cannot land on to where there are only zero pieces blocks or blocks with an enemy or blocks with a wall. And while moving, he cannot get to the 1st block from the nth block, or get to the nth block from the 1st block.
And just like the picture below, the 2nd floor's floor is the 1st floor's ceil:
Now, we have n floors, and each floor has the same width of w blocks, but the number of the pieces of each block can be different. Thus, we can get a map of these floors. Little Eskimo starts from the leftest block on the first floor, unlike the picture above, and we want to use the minimum time to get to the nth floor.(Any block on the nth is all right)
The input contains multiple cases.
In each case, the first line contains two integers represents n and w.(1<=n<=2000 , 1<=w<=100)
The second line contains three integers represents t1, t2, andt3.(0<=t1,t2,t3<=100)
Then the 2n lines, the odd lines contains w characters, describing what is on the floor: '#' represents the enemy, which we assume does not move, '|' represents wall, and '0' represents the block is empty. While the even lines contains w digits from '0' to '9' representing the number of the pieces of each block.
[Notice]: the map inputs from the nth floor downto the 1st floor, that is, the first line of this map describes what is on the nth floor, and the second line of this map describes the number of the pieces of each block of nth floor, or the n-1th floor's ceil.
In each case, output one line with an integer representing the minimum time little Eskimo can get to the nth floor. If there is no way to get to the nth floor, output -1.
This sample input just describe the picture above.
5 22 1 2 3 0000000000000000000000 2222212222122222221222 0000000000000000000000 2122222122222221112222 000000000000000000000# 2222212221222222222111 0000000000000000000000 2222222222112222222221 0000#00000000000000000 1111111111111111111111
Author: Xiong, Siyuan