I - FORCIAN WAY
ผักชี
3
s
1024
MB
800
点
問題文
縦 $3$ マス、横 $N$ マスのマス目があります。
そのうち、いくつかのマス目には英大文字が $1$ つ書かれており、その他のマスには何も書かれていません。
あなたは、まだ文字の書かれていないマス目を好きなだけ選んで、各マスに好きな英大文字を $1$ つ書くことができます。
この操作によって、マス目を次のような状態にできるかを判定してください。
以下、上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。
- $(1,1)$ からスタートし、上下左右に隣接するマスを通って $(3,N)$ をゴールとするマスの列であって、マス目に書かれた文字が
F→O→R→C→I→A→F→O→...→Aとなるもの (順に文字を連結するとFORCIAの 1 回以上の繰り返しとなるもの)が存在する
制約
- $1\leq N \leq 2\times10^5$
- $N$ は整数
- $A_{i,j}$ は英大文字または
.
入力
入力は以下の形式で標準入力から与えられます。
$A_{i,j}$ が . の場合は何も書かれていないマスを、英大文字である場合はその文字が書かれていることを表します。
$N$
$A_{1,1} \cdots A_{1,N}$
$A_{2,1} \cdots A_{2,N}$
$A_{3,1} \cdots A_{3,N}$
出力
問題文の条件を満たすようにできるなら Yes 、できないなら No を出力してください。
入力例 1
6
F..AF.
X.CR.X
.AF..A
出力例 1
Yes
一例として、以下のように書き込むことで、隣接するマスの列 $((1,1), (1,2), (1,3), (2,3), (2,2), (3,2), (3,3), (3,4), (2,4), (2,5), (3,5), (3,6))$ に書かれた文字を順に読むと FORCIAFORCIA となり、問題文の条件を満たすことができます。
FORAF.
XICRCX
.AFOIA
入力例 2
2
..
..
..
出力例 2
Yes
適切に文字を書き込むと条件を満たすことができます。
入力例 3
2
..
..
R.
出力例 3
No
すでに書かれた文字を書き換えたり、$1$ つのマスに $2$ つ以上の文字を書いてはいけません。
入力例 4
3
...
...
...
出力例 4
No
$(3,N)$ の文字はAで終わる必要があります。
入力例 5
8
.Y.U....
...R.U..
..F.UW.A
出力例 5
Yes
入力例 6
12
.THANK.YOU..
...FOR......
....SOLVING.
出力例 6
Yes