루미 알고리즘

#1533플래티넘Laser Chess

PO 2022 결선코딩출제 Fredrik Ekholm, Abdullah Zaghmout영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Fredrik and Abdullah are playing a game of Laser Chess against each other. The game is played on a grid and the objective is to shoot a laser beam at the opponent's king. Abdullah has an attacking piece that, when a button is pressed, shoots laser in all four directions (up, down, left, and right). The attacking piece is marked with A on the grid. Fredrik's king is marked with K. There are also mirror pieces on the grid, marked with o. When a laser hits a mirror piece, the beam bounces out in all four directions.

The game has reached a position where Abdullah will win if he simply presses the button to shoot the laser. To stop Abdullah from winning, Fredrik has now placed smoke bombs on the board, marked with R. The smoke prevents laser beams from traveling through that square. Every second, the smoke spreads to all four adjacent squares. If the attacking piece or the king is in the smoke, Abdullah cannot win.

How many seconds will it take until Abdullah no longer wins by pressing the button? In other words, how many seconds will it take for the smoke to spread so that the laser can no longer reach the king from the attacking piece? It is guaranteed that the game is originally in a position where the laser reaches the king from the attacking piece without passing through any smoke.

Input

The first line contains two integers R and C (1 ≤ R, C and R × C ≤ 40,000), the number of rows and columns in the grid that make up the game board.

The following R lines describe the layout of the game board. The i-th of these lines contains C characters describing the appearance of the i-th row. Each character is one of the following:

  • . for an empty square
  • o for a mirror piece
  • R for a smoke bomb
  • A for the attacking piece
  • K for the king

It is guaranteed that A and K each appear exactly once, that R appears at least once, and that the laser beam initially reaches the king from the attacking piece.

Output

Print the number of seconds it takes until the laser no longer reaches the king.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
110R=1
220There is exactly one R on the board.
320No cell is empty (.)
420R × C ≤ 400
530No additional constraints.

Explanation of Samples

In example case 1, it is optimal for Simon to play the card with value 1 in the first round, and the card with value 2 in the second round. Then Nicole gets |1-1| + |10-2| = 8 points.

In example case 2, Simon plays the cards with values 2, 5, 1, in that order.

In example case 3, Simon plays the cards with values 4, 6, 3, 1, in that order.

예제

예제 1

입력
3 3
.Ao
R..
.Ko
출력
2

예제 2

입력
5 8
A......o
..K.o...
o....o.o
..o..o..
R...o..o
출력
4

예제 3

입력
10 9
oo.o.oRR.
.K.oo..R.
....oo..R
..R......
..R......
A....o.o.
...R.....
.....o.o.
.........
o....o..R
출력
3

출처 표기

출처: Programmeringsolympiaden 2022년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.