만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

말 점프

면접 대비

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

요약
두 말이 체스 나이트처럼 움직이며 돌이 없는 칸에만 착지합니다. 두 말이 도달할 수 있는 칸이 겹치는지 판별합니다.
난이도

쉬움10점 중 3점

유형
BFS, 그래프, 행렬
정답자
아직 제출이 없습니다

문제

빠른 말 Hsara와 Pascal이 NN행 MM열 크기의 2차원 목장에 함께 살고 있다. 목장은 큰 울타리로 둘러싸여 있고, 울타리 안쪽에는 말이 자유롭게 뛸 수 있는 칸이 있다. 두 말은 큰 돌이 있는 칸에 내려앉지 않으려 한다.

점프는 체스의 나이트처럼 한 방향으로 두 칸 가고, 그와 수직인 방향으로 한 칸 간다. 돌을 뛰어넘는 것은 가능하지만, 도착하는 칸은 비어 있어야 한다. 목장의 상태와 두 말의 처음 위치가 주어졌을 때, 두 말이 만날 수 있는지 구하라. 두 말이 같은 칸에 도착할 수 있는 점프 순서가 있으면 만날 수 있다.

입력

첫째 줄에 공백으로 구분된 정수 NN과 MM이 주어진다.

다음 NN개의 줄에는 목장의 각 칸을 나타내는 MM개의 문자가 주어진다. '.'은 빈 칸, '\#'은 돌이 있는 칸, 'H'는 말이 있는 칸이다.

목장은 울타리로 둘러싸여 있다. 입력에는 'H' 칸이 정확히 두 개 있음이 보장된다.

출력

한 줄에 두 말이 만날 수 있으면 "JA", 만날 수 없으면 "NEJ"를 출력한다.

제한

3≤N,M≤5003 \le N, M \le 500

힌트

예제 입력 2를 나타낸 그림이다. Pascal이 뛰어서 Hsara에게 도달하는 방법을 보여 준다.

예제3

  1. 예제 1

    입력
    2 2
    H.
    .H
    
    예상 출력
    NEJ
    
  2. 예제 2

    입력
    3 3
    H.H
    ...
    .#.
    
    예상 출력
    JA
    
  3. 예제 3

    입력
    3 3
    H#H
    ...
    .#.
    
    예상 출력
    NEJ