Problem D
Message
Languages
en
sv
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 \leq N, M \leq 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.
Points
Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.
|
Group |
Point value |
Constraints |
|
$1$ |
$20$ |
$N = 1$ |
|
$2$ |
$40$ |
The number of letters is $N+M-1$. |
|
$3$ |
$40$ |
No additional constraints. |
Explanation of sample 1
![\includegraphics[width=0.3\textwidth ]{sample.PNG}](/problems/meddelande/file/statement/en/img-0001.PNG)
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.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 6 pa.... ...... .u.l.. .....a ...... |
paula |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 sn. .a. .ke |
snake |
