25960번 - 폰의 각성

$N \times N$ 체스판에서의 전쟁 중 상대 나라의 압도적인 병력탓에 준웅나라에는 폰 병사인 선우 혼자만 남게 되었다. 홀로 남게 된 준웅나라의 폰선우는 이러한 절체절명의 위기 속에서 각성하였다! 각성한 폰선우는 한 턴에 다음과 같은 과정을 수행한다.

1. 초기에 폰선우는 가로, 세로, 대각선 $8$방향으로 한 칸 움직일 수 있다. 한 칸 움직여 킹의 위치로 이동했다면, 턴을 종료한다.
2. 폰선우가 도달할 수 있는 칸 중 상대 말이 있는 곳을 하나 선택한다. 상대 말이 있는 칸이 하나도 없다면, 선택이 불가능하고 폰선우의 턴은 종료된다.
3. 폰선우는 선택한 칸으로 이동한다. 선택한 칸에 있던 말은 폰선우에게 능력을 빼앗겨 더 이상 이동할 수 없는 돌이 되고, 폰선우는 빼앗은 이동 방법으로 현재 자신의 이동 방법을 대체한다. 만약, 이동한 위치가 킹의 위치라면 턴을 종료한다. 그렇지 않다면 현 위치에서 2번 과정을 반복한다.

폰선우는 이러한 각성 능력을 이용하여 상대 킹을 잡으러 가야 한다. 상대의 말에는 다음과 같은 종류가 있다.

• 퀸: 가로, 세로, 대각선 $8$방향으로 거리 제한 없이 움직일 수 있다.

• 룩: 가로, 세로 $4$방향으로 거리 제한 없이 움직일 수 있다.

• 비숍: 대각선 $4$방향으로 거리 제한 없이 움직일 수 있다.

• 나이트: 가로, 세로 $4$방향 중 한 방향으로 한 칸, 그리고 그 방향의 양 대각선 방향 중 한 방향으로 한 칸 움직인다. 또한 다른 말을 뛰어넘을 수 있다. 즉, 진행 경로 중간에 장애물이 있어도 체스판을 벗어나지 않는 한 무조건 초록색 칸으로 이동할 수 있다.

대각 이동도 한 칸이라고 친다. 예를 들어 나이트는 상하좌우 중 $1$칸, 대각 $1$칸을 이동하기 때문에 무조건 한 번에 $2$칸씩 이동한다.

폰선우는 한 번 능력을 빼앗아 돌이 된 말에게서 다시 능력을 빼앗을 수 없다. 폰선우는 현재 능력이 나이트인 경우를 제외하면 다른 말들 및 돌이 된 말을 뛰어넘을 수 없다.

폰선우가 한 턴만에 상대 킹을 잡을 수 있다면, 최소 칸 수를 이동하여 상대 킹을 잡을 수 있도록 도와주자. 킹을 잡을 수만 있다면, 체스판에 다른 말들이 남아있어도 상관이 없다.

첫째 줄에 $N$($2 \le N \le 1\,000$)이 주어진다.

둘째 줄부터는 $N$줄에 걸쳐 줄마다 $N$개의 문자가 공백으로 구분되어 주어진다. 이때 0은 빈칸, Q는 퀸, R는 룩, B는 비숍, N은 나이트, K는 킹, P는 폰선우를 의미한다.

킹과 폰선우는 무조건 한 개 존재하고, 퀸은 왕비로서 최대 $1$개만 존재한다.

첫째 줄에 폰선우가 상대 킹을 한 턴 만에 잡을 수 있다면, 최소 몇 칸을 이동하여 잡을 수 있는지를 출력하고, 한 턴 만에 잡을 수 없다면, -1을 출력한다.