영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Group | Points | Constraints |
|---|---|---|
| 1 | 31 | N = 1 |
| 2 | 21 | There are exactly 4 farms that all lie on the corners of the same rectangle. |
| 3 | 48 | No 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.* ..... ..*..