시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 332 120 113 42.966%

문제

크로스워드 퍼즐은 R*C크기의 직사각형으로 이루어져 있고, 각 칸은 비어있거나 막혀있다. 퍼즐은 가로(왼쪽->오른쪽) 또는 세로(위->아래)로 연속된 빈 칸에 단어를 채우면서 푼다.

동혁이는 크로스워드 퍼즐을 풀지 않는다. 그는 풀려있는 퍼즐을 쳐다본다. 그런 후에, 그는 그 퍼즐에서 사전순으로 제일 앞서는 단어를 찾는다. (단어는 적어도 2글자이다.)

크로스워드 퍼즐이 주어졌을 때, 사전순으로 제일 앞서는 단어를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 C (2 ≤ R, C ≤ 20)가 주어진다. R는 행의 개수, C는 열의 개수이다. 그 다음 R개의 줄엔 C개의 문자가 포함되어 있다. 각 문자는 영어 알파벳 소문자 또는 '#'이며, '#'인 경우에는 막혀있는 것이다.

출력

첫째 줄에 사전순으로 제일 앞서는 단어를 출력한다. 정답이 항상 존재하는 경우만 입력으로 주어진다.

예제 입력 1

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

예제 출력 1

kala
W3sicHJvYmxlbV9pZCI6IjMwMDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwNmNcdWI4NWNcdWMyYTRcdWM2Y2NcdWI0ZGMgXHVkMzdjXHVjOTkwIFx1Y2NkMFx1YjJlNFx1YmNmNFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkMDZjXHViODVjXHVjMmE0XHVjNmNjXHViNGRjIFx1ZDM3Y1x1Yzk5MFx1Yzc0MCBSKkNcdWQwNmNcdWFlMzBcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWNlNzhcdWM3NDAgXHViZTQ0XHVjNWI0XHVjNzg4XHVhYzcwXHViMDk4IFx1YjljOVx1ZDYwMFx1Yzc4OFx1YjJlNC4gXHVkMzdjXHVjOTkwXHVjNzQwIFx1YWMwMFx1Yjg1YyhcdWM2N2NcdWNhYmQtJmd0O1x1YzYyNFx1Yjk3OFx1Y2FiZCkgXHViNjEwXHViMjk0IFx1YzEzOFx1Yjg1YyhcdWM3MDQtJmd0O1x1YzU0NFx1Yjc5OClcdWI4NWMgXHVjNWYwXHVjMThkXHViNDFjIFx1YmU0OCBcdWNlNzhcdWM1ZDAgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2M0NFx1YzZiMFx1YmE3NFx1YzExYyBcdWQ0N2NcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQwNmNcdWI4NWNcdWMyYTRcdWM2Y2NcdWI0ZGMgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ4MFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YWRmOFx1YjI5NCBcdWQ0ODBcdWI4MjRcdWM3ODhcdWIyOTQgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1Y2NkMFx1YjJlNFx1YmNmOFx1YjJlNC4gXHVhZGY4XHViN2YwIFx1ZDZjNFx1YzVkMCwgXHVhZGY4XHViMjk0IFx1YWRmOCBcdWQzN2NcdWM5OTBcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YzgxY1x1Yzc3YyBcdWM1NWVcdWMxMWNcdWIyOTQgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2MzZVx1YjI5NFx1YjJlNC4gKFx1YjJlOFx1YzViNFx1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgMlx1YWUwMFx1Yzc5MFx1Yzc3NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1ZDA2Y1x1Yjg1Y1x1YzJhNFx1YzZjY1x1YjRkYyBcdWQzN2NcdWM5OTBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YzgxY1x1Yzc3YyBcdWM1NWVcdWMxMWNcdWIyOTQgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBSXHVhY2ZjIEMgKDIgJmxlOyBSLCBDICZsZTsgMjApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gUlx1YjI5NCBcdWQ1ODlcdWM3NTggXHVhYzFjXHVjMjE4LCBDXHViMjk0IFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgUlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDQgQ1x1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YmIzOFx1Yzc5MFx1YjI5NCZuYnNwO1x1YzYwMVx1YzViNCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwIFx1YjYxMFx1YjI5NCAmIzM5OyMmIzM5O1x1Yzc3NFx1YmE3MCwgJiMzOTsjJiMzOTtcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YjljOVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVjODFjXHVjNzdjIFx1YzU1ZVx1YzExY1x1YjI5NCBcdWIyZThcdWM1YjRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MTVcdWIyZjVcdWM3NzQgXHVkNTZkXHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUFJWQSIsImRlc2NyaXB0aW9uIjoiPHA+TGl0dGxlIEl2aWNhIHNvbHZlcyBjcm9zc3dvcmQgcHV6emxlcyBldmVyeSBkYXkuIEluIGNhc2UgeW91IGhhdmVuJiMzOTt0IHNlZW4gb25lLCBhIGNyb3Nzd29yZCBwdXp6bGUgc3RhcnRzIG9uIGEgZ3JpZCBvZiBSJnRpbWVzO0Mgc3F1YXJlcywgZWFjaCBvZiB3aGljaCBpcyBlaXRoZXIgZW1wdHkgb3IgYmxvY2tlZC4gVGhlIHBsYXllciYjMzk7cyB0YXNrIGlzIHRvIHdyaXRlIHdvcmRzIGluIGNvbnNlY3V0aXZlIGVtcHR5IHNxdWFyZXMgdmVydGljYWxseSAodG9wIGRvd24pIG9yIGhvcml6b250YWxseSAobGVmdCB0byByaWdodCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkl2aWNhJiMzOTtzIHNpc3RlciBoYXMgYSBzdHJhbmdlIGhhYml0IG9mIGxvb2tpbmcgYXQgY3Jvc3N3b3JkcyBJdmljYSBoYXMgZmluaXNoZWQgc29sdmluZywgYW5kIGZpbmRpbmcgdGhlIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXN0IHdvcmQgaW4gaXQuIFNoZSBvbmx5IGNvbnNpZGVycyB3b3JkcyBhdCBsZWFzdCAyIGNoYXJhY3RlcnMgbG9uZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIGEgY3Jvc3N3b3JkIHB1enpsZSwgZmluZHMgdGhhdCB3b3JkLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIFIgYW5kIEMgKDIgJmxlOyBSLCBDICZsZTsgMjApLCB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMgaW4gdGhlIGNyb3Nzd29yZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIFIgbGluZXMgY29udGFpbnMgYSBzdHJpbmcgb2YgQyBjaGFyYWN0ZXJzLiBFYWNoIG9mIHRob3NlIGNoYXJhY3RlcnMgaXMgZWl0aGVyIGEgbG93ZXJjYXNlIGxldHRlciBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldCwgb3IgdGhlIGNoYXJhY3RlciAmIzM5OyMmIzM5OyByZXByZXNlbnRpbmcgYSBibG9ja2VkIHNxdWFyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IHdpbGwgYmUgc3VjaCB0aGF0IGEgc29sdXRpb24gd2lsbCBhbHdheXMgZXhpc3QuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBsZXhpY29ncmFwaGljYWxseSBzbWFsbGVzdCB3b3JkIGluIHRoZSBjcm9zc3dvcmQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #2 3번