P6338 [COCI 2007/2008 #2] PRVA

You are given a crossword grid of symbols of size $r \times c$, consisting of lowercase letters and `#`. A word is a string formed by connecting the letters encountered in the grid from left to right or from top to bottom in order (it must not contain `#`). It does not have to cover an entire row or column, and its length must be at least $2$. For a vertical word, the cell above its first letter and the cell below its last letter must either be `#` or be outside the grid boundary. For a horizontal word, the left of its first letter and the right of its last letter must satisfy the same condition. Please output the lexicographically smallest word.

The first line contains two integers $r, c$, representing the number of rows and columns of the grid. The next $r$ lines each contain $c$ characters describing the grid.

Output one line with some letters, representing the lexicographically smallest word.

#### Constraints For $100\%$ of the testdata, $2 \le r, c \le 20$. #### Note **This problem is translated from [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #2](https://hsin.hr/coci/archive/2007_2008/contest2_tasks.pdf) *T3 PRVA***。 Translated by ChatGPT 5