prithivMLmods/Coder-Stat

1 2<h1><font color="#000000">Problem D:</font> Twirling Robot </h1>3<!-- end en only -->4 5 6 7<!-- begin en only -->8<p>9Let's play a game using a robot on a rectangular board 10covered with a square mesh (Figure D-1).11The robot is initially set at the start square in the northwest corner12facing the east direction.13The goal of this game is to lead the robot14to the goal square in the southeast corner.15</p>16<!-- end en only -->17 18<center>19<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_2008D1"><br><br>20<!-- begin en only -->21Figure D-1: Example of a board22<!-- end en only -->23</center>24 25 26<!-- begin en only -->27<p>28The robot can execute the following five types of commands.29<dl>30<dt> "Straight":</dt>31<dd> Keep the current direction of the robot, and move forward to the next square.</dd>32<dt> "Right":</dt>33<dd> Turn right with 90 degrees from the current direction, and move forward to the next square.</dd>34<dt> "Back":</dt>35<dd> Turn to the reverse direction, and move forward to the next square.</dd>36<dt> "Left":</dt>37<dd> Turn left with 90 degrees from the current direction, and move forward to the next square.</dd>38<dt> "Halt":</dt>39<dd> Stop at the current square to finish the game.</dd>40</dl>41</p>42<!-- end en only -->43 44<!-- begin en only -->45<p>46Each square has one of these commands assigned as shown in Figure D-2.47The robot executes the command assigned to the square where it resides,48unless the player gives another command to be executed instead.49Each time the player gives an explicit command, 50the player has to pay the cost that depends on the command type.51</p>52<!-- end en only -->53 54<center>55<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_2008D2"><br><br>56<!-- begin en only -->57Figure D-2: Example of commands assigned to squares58<!-- end en only -->59</center>60 61 62<!-- begin en only -->63<p>64The robot can visit the same square several times during a game.65The player loses the game when the robot goes out of the board66or it executes a "Halt" command before arriving at the goal square.67</p>68<!-- end en only -->69 70<!-- begin en only -->71<p>72Your task is to write a program that calculates the minimum cost to lead the robot73from the start square to the goal one.74</p>75<!-- end en only -->76 77 78 79<h3>Input</h3>80 81 82<!-- begin en only -->83<p>84The input is a sequence of datasets. 85The end of the input is indicated by a line containing two zeros separated by a space.86Each dataset is formatted as follows.87</p>88<!-- end en only -->89 90<p>91<blockquote>92<i>w h</i><br>93<i>s</i>(1,1)  ... <i>s</i>(1,<i>w</i>)<br>94<i>s</i>(2,1)  ... <i>s</i>(2,<i>w</i>)<br>95...<br>96<i>s</i>(<i>h</i>,1)  ... <i>s</i>(<i><i>h</i></i>,<i>w</i>)<br>97<i>c</i><sub>0</sub> <i>c</i><sub>1</sub> <i>c</i><sub>2</sub> <i>c</i><sub>3</sub>98</blockquote>99</p>100 101 102<!-- begin en only -->103<p>104The integers <i>h</i> and <i>w</i> are the numbers of rows and columns of the board, 105respectively.106You may assume 2 &le; <i>h</i> &le; 30 and 2 &le; <i>w</i> &le; 30. 107Each of the following <i>h</i> lines consists of <i>w</i> numbers delimited by a space.108The number <i>s</i>(<i>i</i>, <i>j</i>) represents the command assigned to the square 109in the <i>i</i>-th row and the <i>j</i>-th column as follows.110<ul>111<li> 0: "Straight"</li> 112<li> 1: "Right"</li>113<li> 2: "Back"</li>114<li> 3: "Left"</li>115<li> 4: "Halt"</li>116</ul>117 118</p>119<!-- end en only -->120 121<!-- begin en only -->122<p>123You can assume that a "Halt" command is assigned to the goal square.124Note that "Halt" commands may be assigned to other squares, too.125</p>126<!-- end en only -->127 128 129<!-- begin en only -->130<p>131The last line of a dataset contains four integers 132<i>c</i><sub>0</sub>, <i>c</i><sub>1</sub>, <i>c</i><sub>2</sub>, and <i>c</i><sub>3</sub>, delimited by a space,  133indicating the costs that the player has to pay 134when the player gives135"Straight", "Right", "Back", and "Left" commands136respectively.137The player cannot give "Halt" commands.138You can assume that all the values of 139<i>c</i><sub>0</sub>, <i>c</i><sub>1</sub>, <i>c</i><sub>2</sub>, and <i>c</i><sub>3</sub>140are between 1 and 9, inclusive.141</p>142<!-- end en only -->143 144 145 146 147 148<h3>Output</h3>149 150<!-- begin en only -->151<p>152For each dataset, print a line only having a decimal integer indicating the minimum cost 153required to lead the robot to the goal.154No other characters should be on the output line.155</p>156<!-- end en only -->157 158 159<h3>Sample Input</h3>160 161<pre>1628 31630 0 0 0 0 0 0 11642 3 0 1 4 0 0 11653 3 0 0 0 0 0 41669 9 1 91674 41683 3 4 01691 2 4 41701 1 1 01710 2 4 41728 7 2 11732 81742 21754 11760 41771 31781 01792 11800 31811 41821 9 3 11830 0184</pre>185 186 187<h3>Output for the Sample Input</h3>188 189<pre>1901191111926193</pre>194 195 196 197 198