Problem B
Roebling Aftermath

Close-up Photo of White and Black Chicken on Tarmac. Photo by Frank Grun

Last night, the festivities on Roebling Avenue got a little out of hand, resulting in quite the mess on around the road. Luckily, this morning there was street cleaning, so the road is now clean. Unfortunately, during last night’s festivities, Alice’s pet chicken got loose and is now lost somewhere on the wrong side of Roebling. The mess on either side of Roebling has unfortunately created obstacles for Alice’s chicken, so it’s having a hard time finding a path to cross the road.

In order to cross Roebling, the chicken must successfully navigate around obstacles to reach the road, and then successfully cross it. Once the chicken reaches the road, it is allowed to walk up and down the newly cleaned road in order to find a place to exit to successfully cross the road. This means in order for the chicken to successfully cross the road, there must be a free space on the other side of the road to allow the chicken to fully get to the other side of the road. Alice’s chicken is quite the dynamic walker, so in order to reach the road it can travel up, down, left, right, and diagonally to navigate around obstacles (i.e. at after every movement the chicken has $8$ potential options to move to next).


The first line of input gives the dimensions $m\times n$ ($0 \le m\cdot n \le 1\, 000\, 000$) of the space where the chicken can walk. The following $m$ lines contain $n$ space-separated characters ’C’, ’X’, ’-’, or ’R’ representing the chicken, obstacles, free spaces, and the road, respectively. The road will always take up one column of the grid in its entirety, and the chicken is guaranteed to start to the left of the road.


Print ”yes” if the chicken is able to successfully cross the road, ”no” otherwise.

Sample Input 1 Sample Output 1
4 4
- - R X
C X R -
- - R X
Sample Input 2 Sample Output 2
4 4
- R X X
C R X -
- R X X
Sample Input 3 Sample Output 3
4 4
- X X R
C - - R
X - X R
- - X R

Please log in to submit a solution to this problem

Log in