시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB188679868344.121%

문제

상근이는 여자친구와의 드라이브를 위해서 운전을 배우고 있다. 도로 연수를 10년쯤 하다 보니 운전은 그럭저럭 잘하게 되었다. 하지만, 그는 유턴을 하지 못한다. 10년동안 도로 연수를 받았지만 유턴을 하지 못한다. 밥먹고 유턴만 연습했지만, 결국 유턴은 하지 못했다.

상근이는 유턴을 연습하기 위해서 시간을 투자하는 대신에 유턴을 할 필요가 없고, 유턴이 금지된 마을로 이사가려고 한다.

상근이가 이사가려고 하는 마을은 막다른 길이 있으면 안 된다. 막다른 길은 유턴을 하지 않고는 빠져나올 수 없기 때문이다. 어떤 마을의 지도가 주어졌을 때, 유턴을 하지 않고 마을의 모든 구역을 돌아다닐 수 있는지 없는지(막다른 길이 있는지 없는지)를 구하는 프로그램을 작성하시오. 

마을의 지도는 R × C 칸으로 이루어진 표로 생각할 수 있다. 각 칸에 빌딩이 있다면 'X'로 표시하고, 길이라면 '.'으로 표시한다. 모든 칸은 빌딩 또는 길이다. 상근이가 어떤 길 위에 있다면, 근처 네 방향(위,아래,오른쪽,왼쪽)의 길로 이동할 수 있다. 빌딩으로는 이동할 수 없다.

이 마을에 막다른 길이 없다면, 상근이는 임의의 한 길에서 시작해서, 갈 수 있는 어떤 방향으로 움직이더라도, 유턴을 하지 않고 그 위치로 돌아올 수 있어야 한다.

유턴은 방금 이동한 방향의 반대 방향으로 이동하는 것을 말한다.

입력

첫째 줄에 마을의 크기 R과 C가 주어진다. (3 ≤ R, C ≤ 10)

다음 R개 줄에는 마을의 지도가 주어진다. 모든 길은 서로 연결되어 있다. 또, 마을에는 적어도 두 개의 길이 있다.

출력

첫째 줄에 마을에 막다른 길이 없다면 0을, 그렇지 않다면 1을 출력한다.

예제 입력 1

4 3
XXX
X.X
X.X
XXX

예제 출력 1

1

예제 입력 2

5 5
XX.XX
X...X
.....
X...X
XX.XX

예제 출력 2

1

예제 입력 3

3 9
...XXX...
.X.....X.
...XXX...

예제 출력 3

0
W3sicHJvYmxlbV9pZCI6IjI4MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjBcdWQxMzQgXHVjMmViXHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNWVjXHVjNzkwXHVjZTVjXHVhZDZjXHVjNjQwXHVjNzU4IFx1YjRkY1x1Yjc3Y1x1Yzc3NFx1YmUwY1x1Yjk3YyBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjNmI0XHVjODA0XHVjNzQ0IFx1YmMzMFx1YzZiMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjNjNFx1Yjg1YyBcdWM1ZjBcdWMyMThcdWI5N2MgMTBcdWIxNDRcdWNiZTQgXHVkNTU4XHViMmU0IFx1YmNmNFx1YjJjOCBcdWM2YjRcdWM4MDRcdWM3NDAgXHVhZGY4XHViN2VkXHVjODAwXHViN2VkIFx1Yzc5OFx1ZDU1OFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhZGY4XHViMjk0IFx1YzcyMFx1ZDEzNFx1Yzc0NCBcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTVjXHViMmU0LiAxMFx1YjE0NFx1YjNkOVx1YzU0OCBcdWIzYzRcdWI4NWMgXHVjNWYwXHVjMjE4XHViOTdjIFx1YmMxYlx1YzU1OFx1YzljMFx1YjljYyBcdWM3MjBcdWQxMzRcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNC4gXHViYzI1XHViYTM5XHVhY2UwIFx1YzcyMFx1ZDEzNFx1YjljYyBcdWM1ZjBcdWMyYjVcdWQ1ODhcdWM5YzBcdWI5Y2MsIFx1YWNiMFx1YWQ2ZCBcdWM3MjBcdWQxMzRcdWM3NDAgXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzcyMFx1ZDEzNFx1Yzc0NCBcdWM1ZjBcdWMyYjVcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWQyMmNcdWM3OTBcdWQ1NThcdWIyOTQgXHViMzAwXHVjMmUwXHVjNWQwIFx1YzcyMFx1ZDEzNFx1Yzc0NCBcdWQ1NjAgXHVkNTQ0XHVjNjk0XHVhYzAwIFx1YzVjNlx1YWNlMCwgXHVjNzIwXHVkMTM0XHVjNzc0IFx1YWUwOFx1YzljMFx1YjQxYyBcdWI5YzhcdWM3NDRcdWI4NWMgXHVjNzc0XHVjMGFjXHVhYzAwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC84YjU3YTg0NS1lMGI0LTRlZTEtYTE2Zi05YTkyNGQ0NjgwZjhcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDU0cHg7IGhlaWdodDogNTRweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Yzc3NFx1YzBhY1x1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHViOWM4XHVjNzQ0XHVjNzQwIFx1YjljOVx1YjJlNFx1Yjk3OCBcdWFlMzhcdWM3NzQgXHVjNzg4XHVjNzNjXHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuIFx1YjljOVx1YjJlNFx1Yjk3OCBcdWFlMzhcdWM3NDAgXHVjNzIwXHVkMTM0XHVjNzQ0IFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFjZTBcdWIyOTQgXHViZTYwXHVjODM4XHViMDk4XHVjNjJjIFx1YzIxOCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWM1YjRcdWI1YTQgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3MjBcdWQxMzRcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWI5YzhcdWM3NDRcdWM3NTggXHViYWE4XHViNGUwIFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWIzY2NcdWM1NDRcdWIyZTRcdWIyZDAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1YzZcdWIyOTRcdWM5YzAoXHViOWM5XHViMmU0XHViOTc4IFx1YWUzOFx1Yzc3NCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNWM2XHViMjk0XHVjOWMwKVx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjNzQ0XHVjNzU4IFx1YzljMFx1YjNjNFx1YjI5NCBSICZ0aW1lczsgQyBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1ZDQ1Y1x1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1Y2U3OFx1YzVkMCBcdWJlNGNcdWI1MjlcdWM3NzQgXHVjNzg4XHViMmU0XHViYTc0ICYjMzk7WCYjMzk7XHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU1OFx1YWNlMCwgXHVhZTM4XHVjNzc0XHViNzdjXHViYTc0ICYjMzk7LiYjMzk7XHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU1Y1x1YjJlNC4gXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc0MCBcdWJlNGNcdWI1MjkgXHViNjEwXHViMjk0IFx1YWUzOFx1Yzc3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzViNFx1YjVhNCBcdWFlMzggXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVhZGZjXHVjYzk4IFx1YjEyNCBcdWJjMjlcdWQ1YTUoXHVjNzA0LFx1YzU0NFx1Yjc5OCxcdWM2MjRcdWI5NzhcdWNhYmQsXHVjNjdjXHVjYWJkKVx1Yzc1OCBcdWFlMzhcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YmU0Y1x1YjUyOVx1YzczY1x1Yjg1Y1x1YjI5NCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjljOFx1Yzc0NFx1YzVkMCBcdWI5YzlcdWIyZTRcdWI5NzggXHVhZTM4XHVjNzc0IFx1YzVjNlx1YjJlNFx1YmE3NCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWQ1NWMgXHVhZTM4XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzExYywgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNWI0XHViNWE0IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWIzNTRcdWI3N2NcdWIzYzQsIFx1YzcyMFx1ZDEzNFx1Yzc0NCBcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YWRmOCBcdWM3MDRcdWNlNThcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWQxMzRcdWM3NDAgXHViYzI5XHVhZTA4IFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWJjMjlcdWQ1YTVcdWM3NTggXHViYzE4XHViMzAwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWM4XHVjNzQ0XHVjNzU4IFx1ZDA2Y1x1YWUzMCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IFIsIEMgJmxlOyAxMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVhZTM4XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YjljOFx1Yzc0NFx1YzVkMFx1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWFlMzhcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWM4XHVjNzQ0XHVjNWQwIFx1YjljOVx1YjJlNFx1Yjk3OCBcdWFlMzhcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0IDBcdWM3NDQsIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQgMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjgyMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9LUkVUIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgYmVlbiBsZWFybmluZyB0byBkcml2ZSwgYnV0IGhlIHN0aWxsIGNhbm5vdCBtYWtlIGEgVS10dXJuIGluIGEgbmFycm93IHN0cmVldC4gVGhhdCZyc3F1bztzIHdoeSBoZSBoYXMgZGVjaWRlZCB0byBnbyBwcmFjdGljZSBpbiBhIHRvd24gd2hlcmUgVS10dXJucyBhcmUgZm9yYmlkZGVuIGV2ZXJ5d2hlcmUuIFRoaXMgcHJvaGliaXRpb24gY2FuIGJlIG1hcmtlZCBieSB0aGUgZm9sbG93aW5nIHNpZ246Jm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvOGI1N2E4NDUtZTBiNC00ZWUxLWExNmYtOWE5MjRkNDY4MGY4XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA1NHB4OyBoZWlnaHQ6IDU0cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPk1pcmtvIGhhcyBzb29uIGZpZ3VyZWQgb3V0IHRoYXQgaGlzIGlkZWFsIHRvd24gbXVzdCBub3QgY29udGFpbiBkZWFkLWVuZCBzdHJlZXRzLCBzaW5jZSBpdCBpcyBpbXBvc3NpYmxlIHRvIGV4aXQgc3VjaCBhIHN0cmVldCB3aXRob3V0IGEgVS10dXJuIChsZXQgdXMgYXNzdW1lIHRoYXQgTWlya28gY2Fubm90IGRyaXZlIGluIHJldmVyc2UgZWl0aGVyKS4gV3JpdGUgYSBwcm9ncmFtIHRvIGFuYWx5c2UgYSB0b3duIG1hcCBhbmQgZGV0ZXJtaW5lIHdoZXRoZXIgdGhlIHRvd24gaXMgc3VpdGFibGUgZm9yIE1pcmtvIChpLmUuIHdoZXRoZXIgdGhlIHRvd24gaGFzIGFueSBkZWFkLWVuZCBzdHJlZXRzKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRvd24gbWFwIGlzIGEgdGFibGUgd2l0aCBSIHggQyBjZWxscywgd2hlcmUgZWFjaCBjZWxsIGlzIGEgYnVpbGRpbmcgc2VnbWVudCAoZGVub3RlZCBieSBYKSBvciBhIHJvYWQgc3VyZmFjZSAoZGVub3RlZCBieSBhIGRvdCkuIEZyb20gYSByb2FkIHN1cmZhY2UgY2VsbCwgTWlya28gY2FuIG1vdmUgdG8gYW55IG9mIHRoZSBzdXJyb3VuZGluZyBmb3VyIGNlbGxzICh1cCwgZG93biwgbGVmdCwgb3IgcmlnaHQpLCBwcm92aWRlZCB0aGF0IGl0IGlzIGFsc28gYSByb2FkIHN1cmZhY2UgKGkuZS4gbm90IGEgYnVpbGRpbmcpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3JtYWxseSwgd2Ugd2lsbCBkZXRlcm1pbmUgdGhhdCBhIHRvd24gaXMgZnJlZSBvZiBkZWFkLWVuZCBzdHJlZXRzIGlmLCBzdGFydGluZyBmcm9tIGFueSByb2FkIHN1cmZhY2UgY2VsbCBhbmQgZ29pbmcgaW4gYW55IG9mIHRoZSBwb3NzaWJsZSBkaXJlY3Rpb25zLCB3ZSBjYW4gcmV0dXJuIHRvIHRoZSBzdGFydGluZyBjZWxsIHdpdGhvdXQgbWFraW5nIGEgMTgwIGRlZ3JlZXMgdHVybiAoY2hhbmdpbmcgb3VyIGRpcmVjdGlvbiB0byB0aGUgb3Bwb3NpdGUgb25lKS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VycyBSIGFuZCBDICgzICZsZTsgUiwgQyAmbGU7IDEwKSwgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIHRvd24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgUiBsaW5lcyBjb250YWlucyBDIGNoYXJhY3RlcnMsIHdpdGggZWFjaCBjaGFyYWN0ZXIgZWl0aGVyICZsZHF1bztYJnJkcXVvOyBvciAmbGRxdW87LiZyZHF1bzsuIFRoZXNlIFIgeCBDIGNoYXJhY3RlcnMgcmVwcmVzZW50IHRoZSB0b3duIG1hcCBhcyBkZXNjcmliZWQgaW4gdGhlIHRleHQgYWJvdmUuIEF0IGxlYXN0IHR3byBjZWxscyB3aWxsIGJlIHJvYWQgc3VyZmFjZXMsIGFuZCBhbGwgcm9hZCBzdXJmYWNlcyB3aWxsIGJlIGNvbm5lY3RlZCAoaS5lLiBtdXR1YWxseSByZWFjaGFibGUpLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gMCBpZiB0aGUgdG93biBpcyBmcmVlIG9mIGRlYWQtZW5kIHN0cmVldHMsIG90aGVyd2lzZSBpdCBtdXN0IGNvbnRhaW4gMS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #2 2번