COCI '07 Contest 2 #3 Prva

Points: 7

Time limit: 0.6s

Memory limit: 32M

Problem type

Little Ivica solves crossword puzzles every day. In case you haven't seen one, a crossword puzzle starts on a grid of $R \times C$ $R \times C$ squares, each of which is either empty or blocked. The player's task is to write words in consecutive empty squares vertically (top down) or horizontally (left to right).

Ivica's sister has a strange habit of looking at crosswords Ivica has finished solving, and finding the lexicographically smallest word in it. She only considers words at least $2$ $2$ characters long.

Write a program that, given a crossword puzzle, finds that word.

Input Specification

The first line contains two integers $R$ $R$ and $C$ $C$ $(2 \le R, C \le 20)$ $(2 \leq R, C \leq 20)$ , the number of rows and columns in the crossword.

Each of the following $R$ $R$ lines contains a string of $C$ $C$ characters. Each of those characters is either a lowercase letter of the English alphabet, or the character '#' representing a blocked square.

The input will be such that a solution will always exist.

Output Specification

Output the lexicographically smallest word in the crossword.

Sample Input 1

Copy

4 4
luka
o#a#
kula
i#a#

Sample Output 1

Copy

kala

Sample Input 2

Copy

4 4
luka
o#a#
kula
i#as

Sample Output 2

Copy

as

Sample Input 3

Copy

4 5
adaca
da##b
abb#b
abbac

Sample Output 3

Copy

abb

Comments

4

Infernape77 commented on Nov. 30, 2017, 9:23 p.m.

why wouldn't the answer be "bb" for sample 3

8

Iamhussam commented on Nov. 30, 2017, 10:59 p.m.

"abb" is lexicographically less than "bb" because it starts with 'a'

2

Infernape77 commented on Dec. 1, 2017, 4:48 a.m.

Oh I didn't realize that it had more priority than the length, thanks