Hide

Lone Rook

/problems/lonerook/file/statement/en/img-0001.png
Rook and knight icons by Cburnett

On a chess board of $r$ rows and $c$ columns there is a lone white rook surrounded by a group of opponent’s black knights. Each knight attacks $8$ squares as in a typical chess game, which are shown in the figure – the knight on the red square attacks the $8$ squares with a red dot. The rook can move horizontally and vertically by any number of squares. The rook can safely pass through an empty square that is attacked by a knight, but it must move to a square that is not attacked by any knight. The rook cannot jump over a knight while moving. If the rook moves to a square that contains a knight, it may capture it and remove it from the board. The black knights never move. Can the rook eventually safely move to the designated target square?

The figure illustrates how the white rook can move to the blue target square at the top-right corner in the first sample case. The rook captures one black knight at the bottom-right of the board on its way.

Input

The first line of input contains two integers $r$ and $c$ ($2 \leq r, c \leq 750$). Each of the next $r$ lines describes one row of the board using $c$ characters: the letter ‘R’ represents the white rook, a ‘K’ represents a black knight, a dot ‘.’ represents an empty square, and the letter ‘T’ represents the white rook’s target square. There is exactly one ‘R’, exactly one ‘T’, and at least one ‘K’ on the board. It is guaranteed that the white rook starts in a square that is not attacked by any knight. The target square may be attacked by a knight, in which case the knight must be captured before the rook can safely move to the target square.

Output

Output yes if the white rook can move to the target square, or no otherwise.

Sample Input 1 Sample Output 1
6 6
.....T
..K.K.
K.K...
....K.
R..K..
....K.
yes
Sample Input 2 Sample Output 2
3 4
RK..
KK..
...T
yes
Sample Input 3 Sample Output 3
4 4
.K..
KR..
K...
.K.T
no
CPU Time limit 11 seconds
Memory limit 1024 MB
Difficulty 6.1hard
Statistics Show
Author
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in