Problem H
Helpful Currents
Lysias loves his full-rigged ship and takes it out to his island castle as often as possible. On his way back to the castle one day, the engines capable of turning the sails failed. As it is a full-rigged ship, he and his crew are now unable to turn the sails in any direction.
But, as luck would have it, there is a south wind which is blowing them in the right direction…at least approximately. Since they may not get to the castle by wind only, Lysias believes he can use the ocean’s currents to move the ship either east or west temporarily by retracting and lowering the ship’s sails. In that way, the ship can move in two potential directions:
-
Move north by lowering the sails
-
Retract the sails and move in the direction of the current they’re on top of (east/west)
Lysias has dug up an old map of all the currents in this part of the ocean. As he is fond of mathematics, not only does Lysias wonder if it’s possible to get home without fixing the sails; he also wonders how many different routes they can take to get home. Can you help him?
Input
The first line has three integers: $Y$ and $X$ and $x_{init}$, representing the number of rows and columns of the map, and which column the ship is currently placed at. The ship always starts on the bottom row.
Then follow $Y$ rows, each with $X$ characters each. All characters $C_{x,y}$ is one of ‘~’, ‘#’, ‘@’, ‘>’ and ‘<’. ’~’ represents open sea without any currents, ‘#’ is impassable shallow waters, and ‘>’ and ‘<’ are currents moving the boat to the right and left respectively. ‘@’ represents Lysias’ castle.
Output
Output all the different distinct paths the ship could take to get back to the castle. Since there may be very many different ways to get back, output the answer modulo $1\, 000\, 003$.
If there are no ways to get to the castle, output “begin repairs”.
Limits
-
$0 < Y \leq 300$
-
$0 \leq x_{init} < X \leq 50\, 000$
-
If $C_{x,y} = \text {‘>’}$, then $x+1 < X$ and $C_{x+1,y} \notin \{ \text {‘<’}, \verb|`#'|\} $
-
If $C_{x,y} = \text {‘<’}$, then $0 \leq x-1$ and $C_{x-1,y} \notin \{ \text {‘>’}, \verb|`#'|\} $
-
There is exactly one ‘@’ tile on the map
-
The boat will not start on a `#' tile
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 0 >@ >~ |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 5 1 >>@<< >~#~< >>>>~ |
4 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 4 0 >~@~ ~<#~ >>>~ |
begin repairs |
