
ZOJ Problem Set  3555
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 i1_{th} block or to the right, the i+1_{th} block as you like, but not the i_{th} 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 0_{th} block or the w+1_{th} 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 1_{st} block from the n_{th} block, or get to the n_{th} block from the 1_{st} block. And just like the picture below, the 2_{nd} floor's floor is the 1_{st} 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 n_{th} floor.(Any block on the n_{th} is all right) InputThe 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 n_{th} floor downto the 1_{st} floor, that is, the first line of this map describes what is on the n_{th} floor, and the second line of this map describes the number of the pieces of each block of n_{th} floor, or the n1_{th} floor's ceil. OutputIn each case, output one line with an integer representing the minimum time little Eskimo can get to the n_{th} floor. If there is no way to get to the n_{th} floor, output 1. Sample InputThis sample input just describe the picture above. 5 22 1 2 3 0000000000000000000000 2222212222122222221222 0000000000000000000000 2122222122222221112222 000000000000000000000# 2222212221222222222111 0000000000000000000000 2222222222112222222221 0000#00000000000000000 1111111111111111111111 Sample Output23 Author: Xiong, Siyuan Contest: ZOJ Monthly, October 2011 