크로스워드에서 가장 앞서는 단어
면접 대비시간 제한1초메모리 제한128 MB
격자에서 가로와 세로로 이어진 길이 2 이상의 글자 시퀀스를 모두 찾아 사전순으로 가장 작은 단어를 출력합니다.
문제
크로스워드 퍼즐은 R x C 크기의 직사각형 격자이다. 각 칸에는 영어 소문자 하나 또는 #이 들어 있으며, #은 막힌 칸을 뜻한다.
단어는 한 행에서 왼쪽에서 오른쪽으로, 또는 한 열에서 위에서 아래로 읽는 막히지 않은 칸들의 최대 연속 구간이다. 길이가 2 이상인 구간만 단어로 본다.
완성된 크로스워드가 주어졌을 때, 격자에 있는 단어 중 사전순으로 가장 앞서는 단어를 출력하라.
입력
첫째 줄에 행의 수 R과 열의 수 C가 주어진다. (2 <= R, C <= 20)
다음 R개의 줄에는 각각 C개의 문자가 주어진다. 각 문자는 영어 소문자 또는 #이다. #은 막힌 칸을 나타낸다.
출력
사전순으로 가장 앞서는 단어를 한 줄에 출력한다.
입력에는 항상 적어도 하나의 올바른 단어가 존재한다.