OpenKattis
Dagy Uppgifter 2 - Grafer

Start

2019-10-24 15:00 CEST

Dagy Uppgifter 2 - Grafer

End

2019-10-31 14:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1866 days 15:54:00

Time elapsed

168:00:00

Time remaining

0:00:00

Problem A
Hesthoppning

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.

Input

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.

Output

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

Förklaring av exempel

\includegraphics[width=0.25\textwidth ]{hestar.png}
Figure 1: En illustration av Sample Input 2 som visar hur Pascal kan hoppa för att nå Hsara.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

1

40

$3 \le N,M \le 100$

2

60

$3 \le N,M \le 500$

Sample Input 1 Sample Output 1
2 2
H.
.H
NEJ
Sample Input 2 Sample Output 2
3 3
H.H
...
.#.
JA
Sample Input 3 Sample Output 3
3 3
H#H
...
.#.
NEJ