크로스워드
면접 대비시간 제한2초메모리 제한128 MB
채워진 크로스워드 격자에서 길이 2 이상인 가로 및 세로 최대 연속 문자열을 모두 찾아 사전순으로 가장 작은 단어를 출력합니다.
문제
동혁이는 크로스워드 퍼즐을 좋아한다. R x C 크기의 완성된 크로스워드 퍼즐이 주어진다. 각 칸에는 알파벳 소문자 하나가 들어 있거나, 단어가 들어갈 수 없는 칸을 나타내는 #이 들어 있다.
퍼즐에서 단어는 가로 또는 세로 방향으로 연속한 두 글자 이상의 알파벳으로 이루어진다. 단어의 양끝은 퍼즐의 경계이거나 #이어야 하므로, 같은 방향으로 더 길게 확장할 수 없어야 한다.
퍼즐에 있는 모든 단어 중 사전순으로 가장 앞서는 단어를 구하시오.
입력
첫째 줄에 퍼즐의 행 수 R과 열 수 C가 공백으로 구분되어 주어진다. (2 <= R, C <= 20)
다음 R개의 줄에는 완성된 퍼즐이 주어진다. 각 줄은 알파벳 소문자 또는 금지된 칸을 나타내는 #으로 이루어진 길이 C의 문자열이다.
입력에는 단어가 하나 이상 존재한다.
출력
퍼즐에 있는 단어 중 사전순으로 가장 앞서는 단어를 한 줄에 출력한다.