Crossword
InterviewTime limit2sMemory limit128 MB
Given a filled crossword grid, extract every maximal horizontal or vertical run of letters of length at least two and output the lexicographically smallest such word.
- Level
Easy3 of 10
- Topics
- String, Implementation, Simulation
- Solved
- No attempts yet
Problem
Donghyuk likes crossword puzzles. You are given a completed crossword puzzle of size R x C. Each cell contains one lowercase English letter or #, which marks a blocked cell where no word can be placed.
A word in the puzzle is a horizontal or vertical sequence of at least two consecutive letters. It must be maximal in that direction: both ends of the sequence are either outside the grid or adjacent to #, so the sequence cannot be extended further.
Find the lexicographically smallest word among all words in the puzzle.
Input
The first line contains the number of rows R and columns C, separated by a space. (2 <= R, C <= 20)
Each of the next R lines describes the completed puzzle. Each line is a string of length C consisting of lowercase English letters and #, where # marks a blocked cell.
The input always contains at least one word.
Output
Print the lexicographically smallest word in the puzzle on one line.