prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem D:</font> Organize Your Train</H1>3 4<p>5In the good old Hachioji railroad station located in the west of Tokyo, there are several parking6lines, and lots of freight trains come and go every day.7</p>8<p>9All freight trains travel at night, so these trains containing various types of cars are settled in10your parking lines early in the morning. Then, during the daytime, you must reorganize cars11in these trains according to the request of the railroad clients, so that every line contains the12“right” train, i.e. the right number of cars of the right types, in the right order.13</p>14<p>15As shown in Figure 7, all parking lines run in the East-West direction. There are exchange16lines connecting them through which you can move cars. An exchange line connects two ends17of different parking lines. Note that an end of a parking line can be connected to many ends of18other lines. Also note that an exchange line may connect the East-end of a parking line and the19West-end of another.20</p>21 22<center>23<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_organizeYourTrain1">24</center>25 26<p>27Cars of the same type are not discriminated between each other. The cars are symmetric, so28directions of cars don’t matter either.29</p>30<p>31You can divide a train at an arbitrary position to make two sub-trains and move one of them32through an exchange line connected to the end of its side. Alternatively, you may move a whole33train as is without dividing it. Anyway, when a (sub-) train arrives at the destination parking34line and the line already has another train in it, they are coupled to form a longer train.35</p>36<p>37Your superautomatic train organization system can do these without any help of locomotive38engines. Due to the limitation of the system, trains cannot stay on exchange lines; when you39start moving a (sub-) train, it must arrive at the destination parking line before moving another40train.41</p>42<p>43In what follows, a letter represents a car type and a train is expressed as a sequence of letters.44For example in Figure 8, from an initial state having a train "<span>aabbccdee</span>" 45on line 0 and no trains46on other lines, you can make "<span>bbaadeecc</span>" on line 2 with the four moves shown in the figure.47</p>48<center>49<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_organizeYourTrain2">50</center>51 52<p>53To cut the cost out, your boss wants to minimize the number of (sub-) train movements. For54example, in the case of Figure 8, the number of movements is 4 and this is the minimum.55</p>56<p>57Given the configurations of the train cars in the morning (arrival state) and evening (departure58state), your job is to write a program to find the optimal train reconfiguration plan.59</p>60 61<H2>Input</H2>62 63<p>64The input consists of one or more datasets. A dataset has the following format:65</p>66 67<pre>68<i>x y</i>69<i>p</i><sub>1</sub> <i>P</i><sub>1</sub> <i>q</i><sub>1</sub> <i>Q</i><sub>1</sub>70<i>p</i><sub>2</sub> <i>P</i><sub>2</sub> <i>q</i><sub>2</sub> <i>Q</i><sub>2</sub>71.72.73.74<i>p</i><sub><i>y</i></sub> <i>P</i><sub><i>y</i></sub> <i>q</i><sub><i>y</i></sub> <i>Q</i><sub><i>y</i></sub>75<i>s</i><sub>0</sub>76<i>s</i><sub>1</sub>77.78.79.80<i>s</i><sub><i>x</i>-1</sub>81<i>t</i><sub>0</sub>82<i>t</i><sub>1</sub>83.84.85.86<i>t</i><sub><i>x</i>-1</sub>87</pre>88 89<p>90<i>x</i> is the number of parking lines, which are numbered from 0 to <i>x</i>-1. <i>y</i> is the number of exchange91lines. Then <i>y</i> lines of the exchange line data follow, each describing two ends connected by the92exchange line; <i>p</i><sub><i>i</i></sub> and <i>q</i><sub><i>i</i></sub> are integers between 0 and <i>x</i> - 1 which indicate parking line numbers,93and <i>P<sub>i</sub></i> and <i>Q<sub>i</sub></i> are either "<span>E</span>" (East) or "<span>W</span>" (West) which indicate the ends of the parking lines.94</p>95<p>96Then <i>x</i> lines of the arrival (initial) configuration data, <i>s</i><sub>0</sub>, ... , <i>s</i><sub><i>x</i>-1</sub>, and <i>x</i> lines of the departure97(target) configuration data, <i>t</i><sub>0</sub>, ... <i>t</i><sub><i>x</i>-1</sub>, follow. Each of these lines contains one or more lowercase letters "<span>a</span>", "<span>b</span>", ..., "<span>z</span>", which indicate types of cars of the train in the corresponding parking98line, in west to east order, or alternatively, a single "<span>-</span>" when the parking line is empty.99</p>100<p>101You may assume that x does not exceed 4, the total number of cars contained in all the trains102does not exceed 10, and every parking line has sufficient length to park all the cars.103</p>104<p>105You may also assume that each dataset has at least one solution and that the minimum number106of moves is between one and six, inclusive.107</p>108<p>109Two zeros in a line indicate the end of the input.110</p>111 112 113<H2>Output</H2>114 115<p>116For each dataset, output the number of moves for an optimal reconfiguration plan, in a separate117line.118 119</p>120 121<H2>Sample Input</H2>122<pre>1233 51240W 1W1250W 2W1260W 2E1270E 1E1281E 2E129aabbccdee130-131-132-133-134bbaadeecc1353 31360E 1W1371E 2W1382E 0W139aabb140bbcc141aa142bbbb143cc144aaaa1453 41460E 1W1470E 2E1481E 2W1492E 0W150ababab151-152-153aaabbb154-155-1560 0157</pre>158 159<H2>Output for the Sample Input</H2>160<pre>161416221635164</pre>165 166 167 168 169