As the ruler of Rainban, you are well aware of the fact that your country often has violent rainstorms. Thus, you usually remember to ride the Rainban Official Motorcade to your destination. Today, however, you looked outside and, eschewing common sense, decided to walk to the store. Now, a very bad storm is coming, and your Giant Hole (TM) umbrella has a large hole in it!
You know the path that you need to travel to return to your home. You are currently standing where the 'Y' is and are trying to reach home (the 'H'). The rest of the path consists of either 'C' or '.', corresponding to whether that section of the path is covered (and thus rain-proof) or uncovered, respectively. Both your current location and home are rain-proof. You also know the forecast, in which the i-th character is 'R' if it is currently raining at the i-th section of the path, or '.' if it is not.
During each minute, the following events happen:
- You choose whether or not to move. If you choose to move, you immediately move one step to an adjacent section of the path. If you choose not to move, you remain in your current section.
- If you are now standing in an uncovered section and it is raining there, you get wet.
- The forecast circularly shifts one section to the left. For example, "R..R" would become "..RR" (quotes for clarity).
- If you are standing in an uncovered section and it is now raining there, you get wet.
So if the path is "Y..H" and the forecast is "R.RR", then choosing to move right every minute would result in the following:
Forecast: R.RR R.RR .RRR .RRR RRR. RRR.
Path: Y..H --> CY.H --> CY.H --> C.YH --> C.YH --> C..Y
You Rain Get You Get Rain Get You Get
move moves wet move wet moves wet move home
Thus, in the above case, you would get wet 3 times on your way home.
Return the minimum number of times that you will get wet before returning home, if you time your journey properly. You don't care how long it takes, as long as you eventually get home while as dry as possible.
|