prithivMLmods/Coder-Stat

1 2 3<h1><font color="#000">Problem D:</font> Cliff Climbing</h1>4<!-- end en only -->5 6 7<!-- begin en only -->8<p>9At 17:00, special agent Jack starts to escape from the enemy camp.10There is a cliff in between the camp and the nearest safety zone.11Jack has to climb the almost vertical cliff 12by stepping his feet on the blocks that cover the cliff.13The cliff has slippery blocks where Jack has to14spend time to take each step. 15He also has to bypass some blocks that are too loose to support his weight.16Your mission is to write a program that calculates the minimum time to complete climbing. 17</p>18<!-- end en only -->19 20<!-- begin en only -->21<p>22Figure D-1 shows an example of cliff data that you will23receive.24The cliff is covered with square blocks.25Jack starts cliff climbing from the ground under the cliff,26by stepping his left or right foot on one of the blocks marked with27'S' at the bottom row.28The numbers on the blocks are the "slippery levels".  It takes29<i>t</i> time units for him to safely put his foot on a30block marked with <i>t</i>, where 1 &le; <i>t</i> &le; 9.31He cannot put his feet on blocks marked with 'X'.32He completes the climbing when he puts 33either of his feet on one of the blocks marked with 'T' at the top row.34</p>35<!-- end en only -->36 37<center>38<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_d-1" border="1"><br>39<!-- begin en only -->40Figure D-1: Example of Cliff Data41<!-- end en only -->42</center>43 44<!-- begin en only -->45<p>46Jack's movement must meet the following constraints. 47After putting his left (or right) foot on a block, he can only move48his right (or left, respectively) foot.49His left foot position (<i>lx</i>, <i>ly</i>) and his right foot position50(<i>rx</i>, <i>ry</i>) should satisfy51<i>lx</i> &lt; <i>rx</i></li> and | <i>lx</i> - <i>rx</i> | + | <i>ly</i> - <i>ry</i> | &le; 3</li>.52This implies that, given a position of his left foot in Figure D-2 (a), he has to53place his right foot on one of the nine blocks marked with blue color.54Similarly, given a position of his right foot in Figure D-2 (b),55he has to place his56left foot on one of the nine blocks marked with blue color.57</p>58<!-- end en only -->59 60<center>61<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_d-2" border="1"><br>62<!-- begin en only -->63Figure D-2: Possible Placements of Feet64<!-- end en only -->65</center>66 67 68 69 70<h2>Input</h2>71 72 73<!-- begin en only -->74<p>75The input is a sequence of datasets.76The end of the input is indicated by a line containing two zeros separated by a space.77Each dataset is formatted as follows:78</p>79<!-- end en only -->80 81<p>82<blockquote>83<i>w h</i><br>84<i>s(1,1)</i>  ... <i>s(1,w)</i><br>85<i>s(2,1)</i>  ... <i>s(2,w)</i><br>86...                                    <br>87<i>s(h,1)</i>  ... <i>s(h,w)</i><br>88</blockquote>89</p>90 91<!-- begin en only -->92<p>93The integers <i>w</i> and <i>h</i> are the width and the height of 94the matrix data of the cliff. You may assume 2 &le; <i>w</i> &le; 30 and 5 &le; <i>h</i> &le; 60.95Each of the following <i>h</i> lines consists of <i>w</i> characters96delimited by a space.97The character <i>s(y, x)</i> represents the state of the block at98position 99(<i>x</i>, <i>y</i>) as follows:100<ul>101<li> 'S': Jack can start cliff climbing from this block. </li>102<li> 'T': Jack finishes climbing when he reaches this block. </li>103<li> 'X': Jack cannot put his feet on this block. </li>104<li> '1' - '9' (<i>= t</i>): Jack has to spend <i>t</i> time units105to put either of his feet on this block. </li>106</ul>107</p>108<p>109You can assume that it takes no time to put a foot on a block marked with 'S' or 'T'.110</p>111 112<!-- end en only -->113 114 115<h2>Output</h2>116 117<!-- begin en only -->118<p>119For each dataset, print a line only having a decimal integer indicating 120the minimum time required for the cliff climbing,121when Jack can complete it.122Otherwise, print a line only having "-1" for the dataset.123Each line should not have any characters other than these numbers.124</p>125<!-- end en only -->126 127 128<h2>Sample Input</h2>129 130<pre>1316 61324 4 X X T T1334 7 8 2 X 71343 X X X 1 81351 2 X X X 61361 1 2 4 4 7137S S 2 3 X X1382 10139T 11401 X1411 X1421 X1431 11441 X1451 X1461 11471 X148S S1492 10150T X1511 X1521 X1531 X1541 11551 X1561 X1571 11581 X159S S16010 10161T T T T T T T T T T162X 2 X X X X X 3 4 X1639 8 9 X X X 2 9 X 91647 7 X 7 3 X X 8 9 X1658 9 9 9 6 3 X 5 X 51668 9 9 9 6 X X 5 X 51678 6 5 4 6 8 X 5 X 51688 9 3 9 6 8 X 5 X 51698 3 9 9 6 X X X 5 X170S S S S S S S S S S17110 71722 3 2 3 2 3 2 3 T T1731 2 3 2 3 2 3 2 3 21743 2 3 2 3 2 3 2 3 41753 2 3 2 3 2 3 2 3 51763 2 3 1 3 2 3 2 3 51772 2 3 2 4 2 3 2 3 5178S S 2 3 2 1 2 3 2 31790 0180</pre>181 182 183<h2>Output for the Sample Input</h2>184 185<pre>186121875188-11892219012191</pre>192 193