34513번 - 룩의 이동

문제

$N \times N$ 크기의 체스판 위에 흑 룩, 백 킹, 그리고 그 외의 흑/백 기물들이 놓여 있다. 여러분은 흑 플레이어이며, 목표는 흑 룩을 이동하여 백 킹을 잡는 것이다.

룩의 이동 규칙은 다음과 같다.

• 한 번의 이동에서 가로 또는 세로 방향으로 원하는 만큼 직선으로 이동할 수 있다. 단, 체스판 밖으로 이동할 수 없다.
• 이동 경로 중 같은 색 기물이 있는 칸은 뛰어넘을 수 없으며, 해당 칸에 멈출 수도 없다.
• 이동 경로 중 다른 색 기물이 있는 칸은 뛰어넘을 수 없지만, 그 칸에 멈춰 해당 기물을 잡을 수 있다.

백 킹 또한 다른 색 기물로 취급된다. 흑 룩이 백 킹을 잡는 데 필요한 최소 이동 횟수를 구해보자.

입력

첫 번째 줄에 $N$이 주어진다.

그다음 줄부터 $N$개의 줄에 걸쳐 체스판의 상태가 주어지며, 각 줄은 길이 $N$의 문자열로 이루어진다. 입력으로 주어지는 문자는 다음과 같다.

• R: 흑 룩
• K: 백 킹
• B: 다른 흑 기물
• W: 다른 백 기물
• .: 빈 칸

체스판에서 흑 룩과 백 킹은 각각 하나만 주어진다. 다른 흑/백 기물은 0ドル$개 이상 주어지며, 일반적인 체스와 달리 개수에 제한이 없다. 같은 칸에 2ドル$개 이상의 기물이 있는 경우는 존재하지 않는다.

출력

만약 흑 룩이 백 킹을 잡을 수 있다면 첫 번째 줄에 필요한 최소 이동 횟수를 출력한다.

만약 흑 룩이 백 킹을 잡을 수 없다면 첫 번째 줄에 -1을 출력한다.

제한

• 2ドル \leq N \leq 1,000円$

힌트