루미 알고리즘

#1659실버The Town Square

PO 2026 학교 예선코딩출제 Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

The archaeologist Arvid is searching for an unknown town square from the Iron Age somewhere in central Sweden. He has mapped a number of farms that existed in the area, and has concluded that the town square must have been at the same distance from each of the farms.

The area Arvid is investigating can be represented by a grid with N rows and M columns. It takes one minute for an Iron Age person to travel between two adjacent cells. Two cells are adjacent if they share one of their four sides.

You are given a map of the grid that marks all positions of farms. It is known that it takes the same amount of time to travel from each of the farms to the town square. Your task is to find which cells the town square could have been located at.

Input

The first line contains the integers N and M (1 ≤ N,M ≤ 10), the number of rows and columns in the grid.

The following N lines each contain a string of length M, consisting of the characters '.' and '*'. These are the rows of the grid. The character '*' means that there is a farm at the corresponding position in the grid, and '.' means that there is not.

There will be at least two farms in the grid. The input has been generated such that there is always at least one cell where the town square could have been.

Output

Print N lines with a string of length M on each line, a copy of the grid from the input but where you have marked with 'X' the cells where the town square could have been located.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

GroupPointsConstraints
131N = 1
221There are exactly 4 farms that all lie on the corners of the same rectangle.
348No additional constraints.

Explanation of Samples

In sample 1, the farms are in the first and last columns of the top row. The third cell on the top row is two minutes from both farms. All cells directly below it have the same distance to both farms: go up to the top row and then equally far to the left or right.

In sample 2, the farms are in the first and seventh columns. The cell in the fourth column is three minutes from both farms. No other cell on the row has the same distance to both.

(그림은 원문 저장소에서 볼 수 있습니다)

The picture shows the solution to sample 3. The marked cell in the center is the only possible position for the town square. It takes two minutes to travel from each farm to this cell.

예제

예제 1

입력
4 5
*...*
.....
.....
.....
출력
*.X.*
..X..
..X..
..X..

예제 2

입력
1 10
*.....*...
출력
*..X..*...

예제 3

입력
5 5
..*..
.....
*...*
.....
..*..
출력
..*..
.....
*.X.*
.....
..*..

출처 표기

출처: Programmeringsolympiaden 2026년 학교 예선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.