루미 알고리즘

#1596브론즈Message

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

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

Problem

In the city where Paula lives, there is a large square. The square can be represented as a grid with N rows and M columns. Some of the grid cells contain engraved letters.

According to a legend, these letters form a message if one walks on the cells in a specific order. To make it correct, one must start in the upper-left corner and end in the lower-right corner, by only moving right and downward. If one manages to visit all cells with engraved letters in this way, the secret message will be revealed.

Paula has decided to crack the mystery once and for all and find the secret message.

Write a program that finds the message given the grid.

Input

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

The following N lines contain a string of length M each. These strings represent the rows in the grid and contain lowercase letters a-z and dots “.”. The dots represent empty cells.

It is guaranteed that it is possible to visit all cells with engraved letters by starting in the upper-left corner and moving right and downward to the lower-right corner.

Output

Print a string, the secret message.

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
120N = 1
240The number of letters is N+M-1.
340No additional constraints.

Explanation of sample 1

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

The image shows the solution to sample case 1. The dark cells represent a possible way to go from the upper-left corner to the lower-right corner, visiting all letters.

예제

예제 1

입력
5 6
pa....
......
.u.l..
.....a
......
출력
paula

예제 2

입력
3 3
sn.
.a.
.ke
출력
snake

출처 표기

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