영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Group | Points | Constraints |
|---|---|---|
| 1 | 20 | N = 1 |
| 2 | 40 | The number of letters is N+M-1. |
| 3 | 40 | No 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