Problemas
체스에서 Knight는 다음과 같이 움직인다.
N 행 N열의 체스판이 주어지고 Knight의 위치, 장애물들의 위치, 그리고 도착점이 주어졌을 때 최소 몇 번을 움직여 Knight가 도착점까지 이동할 수 있는지를 찾아내는 프로그램을 작성하라.
Knight는 장애물이 존재하는 칸으로 움직일 수 없으나, 장애물을 뛰어넘을 수 있다. 또한 Knight는 체스판 밖으로 나갈 수 없다.
Entrada
입력의 첫 번째 줄에는 체스판의 크기 N(4≤N≤50)이 입력된다.
그 다음 에는 N행 N열의 문자가 입력된다. 이는 체스판을 뜻하며, 각 문자는 다음을 의미한다.
K : Knight
O : 장애물
G : 목적지
. : 장애물이 없는 빈칸
Knight가 있는 칸과 목적지에는 장애물이 존재하지 않는다.
Salida
입력에 대해 도착점까지의 Knight의 최소의 이동 횟수를 출력한다.
Ejemplo
4
KOOO
..G.
....
OOOO
1
Fuente
TUD Programming Contest 2001, Darmstadt, Germany, poj 1915
Debes iniciar sesión para escribir código.