Problem I
Railway Runner
Mario decided to outsmart the coolest game of all time “Railway Runner”. But as always he needs your help. Given a railway pattern, he wants to figure out if it is possible to get from one end to the other. Input is given in $N$ horizontal lines, each of which contains three characters denoting the three railways. Each cell can be “*” - part of a train, “.” - rails, and “/” - ladder to the roof of the train. You start on the ground on the first row of cells and your goal is to reach the end of the track, which consists of the cells in the $N$-th row. Here are the rules of the game:
-
You can move left and right between two trains (“*”) or two rails (“.”) that are adjacent to each other, but you cannot go backward (up). No diagonal moves are allowed.
-
You can only get on a train from an adjacent train or via a ladder (“/”).
-
You can jump down on the rails from a train rooftop without hurting yourself. You cannot jump off the train to an adjacent line.
-
Assume the input is valid (i.e. each ladder is followed by a train and preceded by a rail).
-
You can start on any column in the first row as long as it’s a rail (“.”). You can finish on any column in the last row without further restrictions.
-
While on a ladder, you must move forward to the corresponding train roof and climb the ladder.
Input
The first line of input contains a single integer
$N$ ($1 \leq N \leq 100 \, 000$),
representing the length of the railway that you are running
across.
Then follows $N$ lines of
input denoting a row of cells. Each line is a sequence of 3
characters chosen from $[* \; .
\; /]$, representing a train, rail, or ladder
respectively.
Output
Output one line containing either string “YES” or “NO”, depending on if you can reach the other side of the railway.
Sample Input 1 | Sample Output 1 |
---|---|
10 *.* *.. **/ ..* .** .** /** *** *.. .** |
YES |
Sample Input 2 | Sample Output 2 |
---|---|
16 ... /// *** ... *.* ./. .*. .*. .*. .*. .*. /./ *** *** *** ... |
NO |