prithivMLmods/Coder-Stat

1 2<H1><font color="#000000">Problem B:</font> Cleaning Robot</H1>3 4<p>5Dr. Asimov, a robotics researcher, loves to research, but hates houseworks and his house were really dirty. So, he has developed a cleaning robot.6</p>7 8<p>9As shown in the following figure, his house has 9 rooms, where each room is identified by an alphabet:10</p>11 12<br>13<center>14<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_cleaningRobot">15</center>16<br>17 18<p>19The robot he developed operates as follows:20</p>21<ul>22<li>23If the battery runs down, the robot stops.24</li>25<li> If not so, the robot chooses a direction from four cardinal points with the equal probability, and moves to the room in that direction. Then, the robot clean the room and consumes 1 point of the battery. 26</li>27 28<li>29However, if there is no room in that direction, the robot does not move and remains the same room. In addition, there is a junk room in the house where the robot can not enter, and the robot also remains when it tries to enter the junk room. The robot also consumes 1 point of the battery when it remains the same place.30</li>31</ul>32 33<p>34A battery charger for the robot is in a room. It would be convenient for Dr. Asimov if the robot stops at the battery room when its battery run down.35</p>36 37<p>38Your task is to write a program which computes the probability of the robot stopping at the battery room.39</p>40 41<H2>Input</H2>42 43<p>44The input consists of several datasets. Each dataset consists of:45</p>46 47<pre>48<i>n</i>49<i>s t b</i>50</pre>51 52<p>53<i>n</i> is an integer that indicates the initial battery point. <i>s</i>, <i>t</i>, <i>b</i> are alphabets respectively represent the room where the robot is initially, the battery room, and the junk room.54</p>55 56<p>57The input ends with a dataset which consists of single 0 for <i>n</i>. Your program should not output for this dataset.58</p>59 60<H2>Output</H2>61 62<p>63For each dataset, print the probability as a floating point number in a line. The answer may not have an error greater than 0.000001.64</p>65 66<H2>Constraints</H2>67<ul>68<li>Judge data includes at most 100 data sets.</li>69<li><i>n</i> &le; 15</li>70<li><i>s</i>, <i>t</i>, <i>b</i> are distinct.</li>71</ul>72 73<H2>Sample Input</H2>74<pre>75176E A C77178E B C79280E A B81082</pre>83 84<H2>Output for the Sample Input</H2>85<pre>860.00000000870.25000000880.0625000089</pre>90 91