Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Cliff Climbing
Description At 17:00, special agent Jack starts to escape from the enemy camp. There is a cliff in between the camp and the nearest safety zone. Jack has to climb the almost vertical cliff by stepping his feet on the blocks that cover the cliff. The cliff has slippery blocks where Jack has to spend time to take each step. He also has to bypass some blocks that are too loose to support his weight. Your mission is to write a program that calculates the minimum time to complete climbing. Figure D-1 shows an example of cliff data that you will receive. The cliff is covered with square blocks. Jack starts cliff climbing from the ground under the cliff, by stepping his left or right foot on one of the blocks marked with 'S' at the bottom row. The numbers on the blocks are the "slippery levels". It takes Figure D-1: Example of Cliff Data Jack's movement must meet the following constraints. After putting his left (or right) foot on a block, he can only move his right (or left, respectively) foot. His left foot position ( Figure D-2: Possible Placements of Feet Input The input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space. Each dataset is formatted as follows:
The integers - 'S': Jack can start cliff climbing from this block.
- 'T': Jack finishes climbing when he reaches this block.
- 'X': Jack cannot put his feet on this block.
- '1' - '9' (
*= t*): Jack has to spend*t*time units to put either of his feet on this block.
You can assume that it takes no time to put a foot on a block marked with 'S' or 'T'. Output For each dataset, print a line only having a decimal integer indicating the minimum time required for the cliff climbing, when Jack can complete it. Otherwise, print a line only having "-1" for the dataset. Each line should not have any characters other than these numbers. Sample Input 6 6 4 4 X X T T 4 7 8 2 X 7 3 X X X 1 8 1 2 X X X 6 1 1 2 4 4 7 S S 2 3 X X 2 10 T 1 1 X 1 X 1 X 1 1 1 X 1 X 1 1 1 X S S 2 10 T X 1 X 1 X 1 X 1 1 1 X 1 X 1 1 1 X S S 10 10 T T T T T T T T T T X 2 X X X X X 3 4 X 9 8 9 X X X 2 9 X 9 7 7 X 7 3 X X 8 9 X 8 9 9 9 6 3 X 5 X 5 8 9 9 9 6 X X 5 X 5 8 6 5 4 6 8 X 5 X 5 8 9 3 9 6 8 X 5 X 5 8 3 9 9 6 X X X 5 X S S S S S S S S S S 10 7 2 3 2 3 2 3 2 3 T T 1 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 4 3 2 3 2 3 2 3 2 3 5 3 2 3 1 3 2 3 2 3 5 2 2 3 2 4 2 3 2 3 5 S S 2 3 2 1 2 3 2 3 0 0 Sample Output 12 5 -1 22 12 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator