COCI '07 Contest 2 #3 Prva

View as PDF

Submit solution

Points: 7
Time limit: 0.6s
Memory limit: 32M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 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 characters long.

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

Input Specification

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

Each of the following R lines contains a string of 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

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

Sample Output 1

kala

Sample Input 2

4 4
luka
o#a#
kula
i#as

Sample Output 2

as

Sample Input 3

4 5
adaca
da##b
abb#b
abbac

Sample Output 3

abb

Comments


  • 0
    Infernape77  commented on Nov. 30, 2017, 4:23 p.m.

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


    • 4
      Iamhussam  commented on Nov. 30, 2017, 5:59 p.m.

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


      • 0
        Infernape77  commented on Nov. 30, 2017, 11:48 p.m.

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