나이트와 킹

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

요약
넓은 체스판에서 로하는 나이트, 한양이는 킹을 번갈아 움직일 때, 로하가 정해진 위치에 먼저 도달할 수 있는지 판정한다.
난이도

어려움10점 중 8점

유형
게임 이론, BFS, 수학, 구현
정답자
아직 제출이 없습니다

문제

로하와 한양이는 ”나이트와 킹” 게임을 하고 있다. 게임의 규칙은 다음과 같다.

  • 게임은 NN행 MM열의 체스판 위에서 진행된다.
  • 체스판의 위에서부터 ii번째 행, 왼쪽에서부터 jj번째 열의 칸의 위치를 (i,j)(i,j)라고 하자.
  • 게임을 시작할 때 말은 (x_1,y_1)(x\_1,y\_1)에 놓여 있다.
  • 로하와 한양이는 로하부터 시작해 번갈아 가며 차례를 진행한다.
  • 로하의 차례에는 체스의 나이트 이동 규칙으로 말을 한 번 이동해야 한다.
  • 한양이의 차례에는 체스의 킹 이동 규칙으로 말을 한 번 이동해야 한다.
  • 말이 총 1010010^{100}번 이동하기 전에 (x_2,y_2)(x\_2,y\_2)에 도달한다면 로하의 승리, 그렇지 않다면 한양이의 승리이다.
  • 체스의 나이트와 킹의 이동 규칙은 노트를 참고하라.

로하와 한양이가 최적의 전략으로 게임을 플레이한다면 누가 승리할 지 알아내라.

입력

첫째 줄에 체스판의 행의 수 NN과 열의 수 MM이 공백으로 구분되어 주어진다. (4≤N,M≤1,0004 \leq N, M \leq 1\\,000)

둘째 줄에 처음 말이 놓이는 위치 x_1,y_1x\_1, y\_1과 로하가 말을 도달시켜야 하는 위치 x_2,y_2x\_2, y\_2가 공백으로 구분되어 주어진다. 두 위치는 서로 다르다. (1≤x_1,x_2≤N1 \leq x\_1, x\_2 \leq N; 1≤y_1,y_2≤M1 \leq y\_1, y\_2 \leq M)

출력

첫째 줄에 로하가 승리한다면 LOHA, 한양이가 승리한다면 HANYANG을 대문자로 출력한다.

힌트

체스에서 나이트와 킹은 다음과 같이 이동할 수 있다.

나이트는 가로로 22칸, 세로로 11칸 이동하거나 가로로 11칸, 세로로 22칸 이동할 수 있다.

킹은 가로, 세로, 대각선으로 인접한 칸으로 이동할 수 있다.

예제2

  1. 예제 1

    입력
    4 4
    1 1 4 4
    
    예상 출력
    HANYANG
    
  2. 예제 2

    입력
    4 4
    2 2 3 4
    
    예상 출력
    LOHA