Problem G
Protecting the Collection
Nathaniel collects rare gems and minerals, and has decided he has to protect his valuable collection from thieves. He is installing an electric eye system, in which he shines a laser into the room with his collection, and the laser will hit a sensor as long as no one steps in a spot that the laser crosses. Unfortunately, he spent most of his money on his collection, so he has only one laser and one sensor, and some mirrors. He has installed the mirrors at various locations in the room, at $45$ degree angles to the walls. At the point you have been called in to help, he has only one more mirror left to install, and he wants to know if there is any way to place it such that the laser will reach the sensor (as long as no one is in its way).
We will assume that the room is always square, the laser is always in the northern wall pointing south, and the sensor is mounted on the eastern wall, such that the laser must hit it from the west. We will also assume that the interior of the room can be represented by a grid, and that all mirrors (including the one to be added) are placed at the center of grid cells, at $45$ degrees with respect to the grid axis, and that the laser and sensor are at the center of their respective column/row of the grid.
Input
The first line of the input contains three integers: $n$, the size of the room, $c$, the column number of the laser ($1\leq c\leq n$), and $r$, the row number of the sensor ($1\leq r\leq n$). This is followed by $n$ lines, each containing $n$ characters separated by spaces. The character . represents an empty space, the character \ represents a mirror oriented NW/SE and the character / represents a mirror oriented NE/SW. You may assume $1\leq n\leq 2\, 000$ and $1\leq r,c\leq n$.
Output
The output should consist of the string YES if the laser can be made to hit the sensor with the addition of at most one mirror, or the string NO otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 2 3 . . . . . . . . . . . . \ . . . \ . . . . . . . . |
NO |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 2 3 . . . . . / / . \ . . . . \ . \ . . . . . . . . . |
YES |
