Hesthoppning

시간 제한6초메모리 제한1024 MB

요약

바위가 있는 격자에서 두 나이트가 바위를 뛰어넘어 이동할 수 있을 때, 둘이 같은 칸에서 만날 수 있는지 판정한다.

난이도: 보통10점 중 6점
유형: 그래프, BFS, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

De snela hestarna Hsara och Pascal bor tillsammans i en tvådimensionell hage av storlek $N$ rader och $M$ kolumner. Hagen är omgiven av ett stort stängsel, men innanför det så finns det rutor där hestarna kan hoppa fritt. De vill dock båda undvika att hoppa på rutor där det ligger stora stenar.

För de som spelat schack så är det välkänt att ett hopp går till genom att ta två steg i en riktning och ett steg i en riktning vinkelrät mot den första. Det är möjligt att hoppa över stenar, men rutan som man landar i måste vara fri. Givet hur hagen ser ut, och var hestarna befinner sig från början, så vill de veta om det är möjligt för dem att träffas. De kan träffas om det finns något sätt de kan hoppa på så att de hamnar på samma ruta. Hjälp dem att ta reda på det.

입력

Den första raden innehåller heltalen $N$ och $M$ , separerade med ett blanksteg.

De nästa $N$ raderna består av $M$ tecken som var och en beskriver hur en ruta i hagen ser ut. Ett '.' innebär att rutan är tom, '\#' beskriver en ruta med en sten i, och 'H' betyder att en av hestarna står i den här rutan.

Hagen är omgiven av stängsel. Det är garanterat att indata alltid innehåller exakt två 'H'-celler.

출력

Ditt program ska skriva ut ett ord på en rad - "JA" om hestarna kan mötas på någon cell och "NEJ" annars.

제한

$3 \le N,M \le 500$

힌트

En illustration av Sample Input 2 som visar hur Pascal kan hoppa för att nå Hsara.

예제3

예제 1
입력
```
2 2
H.
.H
```
예상 출력
```
NEJ
```
예제 2
입력
```
3 3
H.H
...
.#.
```
예상 출력
```
JA
```
예제 3
입력
```
3 3
H#H
...
.#.
```
예상 출력
```
NEJ
```