나이트와 킹
시간 제한1초메모리 제한1024 MB
넓은 체스판에서 로하는 나이트, 한양이는 킹을 번갈아 움직일 때, 로하가 정해진 위치에 먼저 도달할 수 있는지 판정한다.
문제
로하와 한양이는 ”나이트와 킹” 게임을 하고 있다. 게임의 규칙은 다음과 같다.
- 게임은 행 열의 체스판 위에서 진행된다.
- 체스판의 위에서부터 번째 행, 왼쪽에서부터 번째 열의 칸의 위치를 라고 하자.
- 게임을 시작할 때 말은 에 놓여 있다.
- 로하와 한양이는 로하부터 시작해 번갈아 가며 차례를 진행한다.
- 로하의 차례에는 체스의 나이트 이동 규칙으로 말을 한 번 이동해야 한다.
- 한양이의 차례에는 체스의 킹 이동 규칙으로 말을 한 번 이동해야 한다.
- 말이 총 번 이동하기 전에 에 도달한다면 로하의 승리, 그렇지 않다면 한양이의 승리이다.
- 체스의 나이트와 킹의 이동 규칙은 노트를 참고하라.
로하와 한양이가 최적의 전략으로 게임을 플레이한다면 누가 승리할 지 알아내라.
입력
첫째 줄에 체스판의 행의 수 과 열의 수 이 공백으로 구분되어 주어진다. ()
둘째 줄에 처음 말이 놓이는 위치 과 로하가 말을 도달시켜야 하는 위치 가 공백으로 구분되어 주어진다. 두 위치는 서로 다르다. (; )
출력
첫째 줄에 로하가 승리한다면 LOHA, 한양이가 승리한다면 HANYANG을 대문자로 출력한다.
힌트
체스에서 나이트와 킹은 다음과 같이 이동할 수 있다.
나이트는 가로로 칸, 세로로 칸 이동하거나 가로로 칸, 세로로 칸 이동할 수 있다.
킹은 가로, 세로, 대각선으로 인접한 칸으로 이동할 수 있다.

