레이저 체스

Fredrik과 Abdullah는 서로 Laser Chess 게임을 하고 있다. 게임은 격자에서 진행되며, 목표는 상대방의 왕에게 레이저 광선을 쏘는 것이다. Abdullah에게는 버튼을 누르면 네 방향(위, 아래, 왼쪽, 오른쪽) 모두로 레이저를 쏘는 공격 기물이 있다. 공격 기물은 격자에서 A로 표시된다. Fredrik의 왕은 K로 표시된다. 격자에는 o로 표시되는 거울 기물도 있다. 레이저가 거울 기물에 닿으면 광선은 네 방향 모두로 튕겨 나간다.

게임은 Abdullah가 버튼을 눌러 레이저를 쏘기만 하면 이기는 상황에 이르렀다. Abdullah가 이기는 것을 막기 위해 Fredrik은 이제 보드에 R로 표시되는 연막탄을 놓았다. 연기는 레이저 광선이 그 칸을 통과하지 못하게 한다. 매초 연기는 인접한 네 칸 모두로 퍼진다. 공격 기물이나 왕이 연기 속에 있으면 Abdullah는 이길 수 없다.

Abdullah가 버튼을 눌러도 더 이상 이기지 못하게 되기까지 몇 초가 걸리는가? 다시 말해, 공격 기물에서 나온 레이저가 더 이상 왕에게 도달할 수 없도록 연기가 퍼지는 데 몇 초가 걸리는가? 처음에는 레이저가 어떤 연기도 통과하지 않고 공격 기물에서 왕에게 도달하는 상황임이 보장된다.

채점

여러 테스트 그룹으로 구성된 테스트 세트로 풀이를 평가하며, 각 그룹에는 일정한 점수가 배정되어 있다. 각 테스트 그룹은 여러 테스트 케이스로 구성된다. 테스트 그룹의 점수를 얻으려면 해당 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$10$| $R=1$

$2$ |$20$| 보드에 R가 정확히 하나 있다.

$3$ |$20$| 빈 칸이 없다. (.)

$4$ |$20$| $R\times C \leq 400$

$5$ |$30$| 추가 제한 조건이 없다.

첫째 줄에는 게임 보드를 이루는 격자의 행과 열의 개수를 나타내는 두 정수 $R$와 $C$가 주어진다. ($1 \le R, C$ 및 $R \times C \le 40,000$)

다음 $R$개의 줄은 게임 보드의 배치를 나타낸다. 이 줄들 중 $i$번째 줄에는 $i$번째 행의 모습을 나타내는 $C$개의 문자가 주어진다. 각 문자는 다음 중 하나이다.

• 빈 칸을 나타내는 .

• 거울 기물을 나타내는 o

• 연막탄을 나타내는 R

• 공격 기물을 나타내는 A

• 왕을 나타내는 K

A와 K는 각각 정확히 한 번씩 등장하고, R는 적어도 한 번 등장하며, 처음에는 공격 기물에서 나온 레이저 광선이 왕에게 도달함이 보장된다.

레이저가 더 이상 왕에게 도달하지 않게 되기까지 걸리는 시간을 초 단위로 출력한다.

예제 케이스 1에서는 Simon이 첫 라운드에 값이 1인 카드를 내고, 둘째 라운드에 값이 2인 카드를 내는 것이 최적이다. 그러면 Nicole은 $|1-1| + |10-2| = 8$점을 얻는다.

예제 케이스 2에서 Simon은 값이 2, 5, 1인 카드를 그 순서대로 낸다.

예제 케이스 3에서 Simon은 값이 4, 6, 3, 1인 카드를 그 순서대로 낸다.