시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB5581167117.275%

문제

N×M 크기의 감옥이 있다. 감옥은 스코필드가 미리 뚫어 놓은 탈출구, 벽, 그리고 빈 칸으로 이루어져 있는데 각각의 모든 빈 칸에는 사람이 한 명씩 있다. 감옥 안에 있는 모든 사람들은 탈출구를 통해 탈옥을 해 내야 한다. 물론, 최대한 빨리 모든 사람이 탈출하도록 하고 싶다.

각 사람이 한 칸을 이동하는 데에는 1초가 걸리며, 하나의 탈출구를 통해서는 1초에 한 사람만 탈출을 할 수 있다. 그리고 사람들이 탈출하는 동안에는 하나의 빈 칸에 여러 명의 사람들이 있어도 된다. 감옥의 정보가 주어져 있을 때, 사람들이 모두 탈출하려면 모두 몇 초의 시간이 걸리는지 구하는 프로그램을 작성하시오.

감옥의 가장자리는 반드시 벽 또는 탈출구이며, 안쪽에는 탈출구가 없다. 탈출구가 없을 수도 있고, 감옥에는 빈 칸이 하나 이상 있다.

입력

첫째 줄에 감옥의 행의 수와 열의 수, N, M이 공백을 사이에 두고 주어진다. 그리고 N개의 줄에 걸쳐서 감옥의 정보가 주어진다. ‘X'는 벽을 의미하고 '.'은 빈 칸, 'D'는 스코필드가 미리 뚫어 놓은 탈출구 위치를 의미한다.

출력

첫째 줄에 모든 사람이 탈출을 하는 최소시간을 출력한다. 만약에 모두 탈출하는 것이 불가능하다면 “impossible"을 출력한다.

제한

  • 3 ≤ N, M ≤ 12

예제 입력 1

5 5
XXDXX
X...X
D...X
X...D
XXXXX

예제 출력 1

3

예제 입력 2

5 5
XDXXX
X.X.D
XX.XX
D.X.X
XXXDX

예제 출력 2

impossible
W3sicHJvYmxlbV9pZCI6IjE4ODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1MDRcdWI5YWNcdWM5OGMgXHViZTBjXHViODA4XHVjNzc0XHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5OJnRpbWVzO00gXHVkMDZjXHVhZTMwXHVjNzU4IFx1YWMxMFx1YzYyNVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWMxMFx1YzYyNVx1Yzc0MCBcdWMyYTRcdWNmNTRcdWQ1NDRcdWI0ZGNcdWFjMDAgXHViYmY4XHViOWFjIFx1YjZhYlx1YzViNCBcdWIxOTNcdWM3NDAgXHVkMGM4XHVjZDljXHVhZDZjLCBcdWJjYmQsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWJlNDggXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTRcdWIzNzAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJlNDggXHVjZTc4XHVjNWQwXHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWQ1NWMgXHViYTg1XHVjNTI5IFx1Yzc4OFx1YjJlNC4gXHVhYzEwXHVjNjI1IFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWQwYzhcdWNkOWNcdWFkNmNcdWI5N2MgXHVkMWI1XHVkNTc0IFx1ZDBjOFx1YzYyNVx1Yzc0NCBcdWQ1NzQgXHViMGI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViYjNjXHViODYwLCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViZTY4XHViOWFjIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkMGM4XHVjZDljXHVkNTU4XHViM2M0XHViODVkIFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkNTVjIFx1Y2U3OFx1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViMzcwXHVjNWQwXHViMjk0IDFcdWNkMDhcdWFjMDAgXHVhYzc4XHViOWFjXHViYTcwLCBcdWQ1NThcdWIwOThcdWM3NTggXHVkMGM4XHVjZDljXHVhZDZjXHViOTdjIFx1ZDFiNVx1ZDU3NFx1YzExY1x1YjI5NCAxXHVjZDA4XHVjNWQwIFx1ZDU1YyBcdWMwYWNcdWI3OGNcdWI5Y2MgXHVkMGM4XHVjZDljXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1ZDBjOFx1Y2Q5Y1x1ZDU1OFx1YjI5NCBcdWIzZDlcdWM1NDhcdWM1ZDBcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YmU0OCBcdWNlNzhcdWM1ZDAgXHVjNWVjXHViN2VjIFx1YmE4NVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjNzg4XHVjNWI0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHVhYzEwXHVjNjI1XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWQwYzhcdWNkOWNcdWQ1NThcdWI4MjRcdWJhNzQgXHViYWE4XHViNDUwIFx1YmE4NyBcdWNkMDhcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjlhY1x1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVhYzEwXHVjNjI1XHVjNzU4IFx1YWMwMFx1YzdhNVx1Yzc5MFx1YjlhY1x1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHViY2JkIFx1YjYxMFx1YjI5NCBcdWQwYzhcdWNkOWNcdWFkNmNcdWM3NzRcdWJhNzAsIFx1YzU0OFx1Y2FiZFx1YzVkMFx1YjI5NCBcdWQwYzhcdWNkOWNcdWFkNmNcdWFjMDAgXHVjNWM2XHViMmU0LiBcdWQwYzhcdWNkOWNcdWFkNmNcdWFjMDAgXHVjNWM2XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWFjZTAsIFx1YWMxMFx1YzYyNVx1YzVkMFx1YjI5NCBcdWJlNDggXHVjZTc4XHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzEgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMTBcdWM2MjVcdWM3NTggXHVkNTg5XHVjNzU4IFx1YzIxOFx1YzY0MCBcdWM1ZjRcdWM3NTggXHVjMjE4LCBOLCBNXHVjNzc0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWFjMTBcdWM2MjVcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJmxzcXVvO1gmIzM5O1x1YjI5NCBcdWJjYmRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTU4XHVhY2UwICYjMzk7LiYjMzk7XHVjNzQwIFx1YmU0OCBcdWNlNzgsICYjMzk7RCYjMzk7XHViMjk0IFx1YzJhNFx1Y2Y1NFx1ZDU0NFx1YjRkY1x1YWMwMCBcdWJiZjhcdWI5YWMgXHViNmFiXHVjNWI0IFx1YjE5M1x1Yzc0MCBcdWQwYzhcdWNkOWNcdWFkNmMgXHVjNzA0XHVjZTU4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkMGM4XHVjZDljXHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGNcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2RcdWM1ZDAgXHViYWE4XHViNDUwIFx1ZDBjOFx1Y2Q5Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViMmU0XHViYTc0ICZsZHF1bztpbXBvc3NpYmxlJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MyAmbGU7IE4sIE0gJmxlOyAxMjxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMTg4NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkV2YWN1YXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPkZpcmVzIGNhbiBiZSBkaXNhc3Ryb3VzLCBlc3BlY2lhbGx5IHdoZW4gYSBmaXJlIGJyZWFrcyBvdXQgaW4gYSByb29tIHRoYXQgaXMgY29tcGxldGVseSBmaWxsZWQgd2l0aCBwZW9wbGUuIFJvb21zIHVzdWFsbHkgaGF2ZSBhIGNvdXBsZSBvZiBleGl0cyBhbmQgZW1lcmdlbmN5IGV4aXRzLCBidXQgd2l0aCBldmVyeW9uZSBydXNoaW5nIG91dCBhdCB0aGUgc2FtZSB0aW1lLCBpdCBtYXkgdGFrZSBhIHdoaWxlIGZvciBldmVyeW9uZSB0byBlc2NhcGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIGZsb29ycGxhbiBvZiBhIHJvb20gYW5kIG11c3QgZmluZCBvdXQgaG93IG11Y2ggdGltZSBpdCB3aWxsIHRha2UgZm9yIGV2ZXJ5b25lIHRvIGdldCBvdXQuIFJvb21zIGNvbnNpc3Qgb2Ygb2JzdGFjbGVzIGFuZCB3YWxscywgd2hpY2ggYXJlIHJlcHJlc2VudGVkIG9uIHRoZSBtYXAgYnkgYW4gJiMzOTtYJiMzOTssIGVtcHR5IHNxdWFyZXMsIHJlcHJlc2VudGVkIGJ5IGEgJiMzOTsuJiMzOTsgYW5kIGV4aXQgZG9vcnMsIHdoaWNoIGFyZSByZXByZXNlbnRlZCBieSBhICYjMzk7RCYjMzk7LiBUaGUgYm91bmRhcnkgb2YgdGhlIHJvb20gY29uc2lzdHMgb25seSBvZiBkb29ycyBhbmQgd2FsbHMsIGFuZCB0aGVyZSBhcmUgbm8gZG9vcnMgaW5zaWRlIHRoZSByb29tLiBUaGUgaW50ZXJpb3Igb2YgdGhlIHJvb20gY29udGFpbnMgYXQgbGVhc3Qgb25lIGVtcHR5IHNxdWFyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW5pdGlhbGx5LCB0aGVyZSBpcyBvbmUgcGVyc29uIG9uIGV2ZXJ5IGVtcHR5IHNxdWFyZSBpbiB0aGUgcm9vbSBhbmQgdGhlc2UgcGVyc29ucyBzaG91bGQgbW92ZSB0byBhIGRvb3IgdG8gZXhpdC4gVGhleSBjYW4gbW92ZSBvbmUgc3F1YXJlIHBlciBzZWNvbmQgdG8gdGhlIE5vcnRoLCBTb3V0aCwgRWFzdCBvciBXZXN0LiBXaGlsZSBldmFjdWF0aW5nLCBtdWx0aXBsZSBwZXJzb25zIGNhbiBiZSBvbiBhIHNpbmdsZSBzcXVhcmUuIFRoZSBkb29ycyBhcmUgbmFycm93LCBob3dldmVyLCBhbmQgb25seSBvbmUgcGVyc29uIGNhbiBsZWF2ZSB0aHJvdWdoIGEgZG9vciBwZXIgc2Vjb25kLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XaGF0IGlzIHRoZSBtaW5pbWFsIHRpbWUgbmVjZXNzYXJ5IHRvIGV2YWN1YXRlIGV2ZXJ5Ym9keT8gQSBwZXJzb24gaXMgZXZhY3VhdGVkIGF0IHRoZSBtb21lbnQgaGUgb3Igc2hlIGVudGVycyBhIGRvb3Igc3F1YXJlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRvIGZvbGxvdy4gRWFjaCB0ZXN0IGNhc2UgaGFzIHRoZSBmb2xsb3dpbmcgZm9ybWF0OiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdHdvIGludGVnZXJzIFkgYW5kIFgsIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSwgc2F0aXNmeWluZyAzICZsZTsgWSwgWCAmbGU7IDEyOiB0aGUgc2l6ZSBvZiB0aGUgcm9vbSZuYnNwOzxcL2xpPlxyXG5cdDxsaT5ZIGxpbmVzIHdpdGggWCBjaGFyYWN0ZXJzLCBlYWNoIGNoYXJhY3RlciBiZWluZyBlaXRoZXIgJiMzOTtYJiMzOTssICYjMzk7LiYjMzk7LCBvciAmIzM5O0QmIzM5OzogYSB2YWxpZCBkZXNjcmlwdGlvbiBvZiBhIHJvb208XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBldmVyeSB0ZXN0IGNhc2UgaW4gdGhlIGlucHV0LCB0aGUgb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIGxpbmUgd2l0aCB0aGUgbWluaW1hbCBldmFjdWF0aW9uIHRpbWUgaW4gc2Vjb25kcywgaWYgZXZhY3VhdGlvbiBpcyBwb3NzaWJsZSwgb3IgJnF1b3Q7aW1wb3NzaWJsZSZxdW90OywgaWYgaXQgaXMgbm90LiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d