레이팅 미적용설명
어린 Ivica는 매일 십자말풀이를 푼다. 혹시 본 적이 없다면, 십자말풀이는 \(R \times C\)개의 칸으로 이루어진 격자에서 시작하는데, 각 칸은 비어 있거나 막혀 있다. 플레이어의 과제는 연속된 빈 칸들에 세로(위에서 아래로) 또는 가로(왼쪽에서 오른쪽으로)로 단어를 적는 것이다.
Ivica의 여동생은 Ivica가 다 푼 십자말풀이를 들여다보며, 그 안에서 사전순으로 가장 앞서는 단어를 찾는 이상한 습관이 있다. 그녀는 길이가 \(2\)자 이상인 단어만 고려한다.
십자말풀이가 주어졌을 때 그 단어를 찾는 프로그램을 작성하시오.
제약
입력 형식
첫째 줄에 십자말풀이의 행 수와 열 수인 두 정수 \(R\)과 \(C\) (\(2 \le R, C \le 20\))가 주어진다.
다음 \(R\)개의 줄에는 \(C\)개의 문자로 이루어진 문자열이 주어진다. 각 문자는 영어 알파벳 소문자이거나, 막힌 칸을 나타내는 문자 #이다.
입력은 해가 항상 존재하도록 주어진다.
출력 형식
십자말풀이에서 사전순으로 가장 앞서는 단어를 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 40점 |
예제 1
입력
4 4
luka
o#a#
kula
i#a#출력
kala예제 2
입력
4 4
luka
o#a#
kula
i#as출력
as예제 3
입력
4 5
adaca
da##b
abb#b
abbac출력
abb문제 정보
태그