시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 269 50 28 15.909%

문제

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

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

감옥의 가장자리는 반드시 벽 또는 탈출구이며, 안쪽에는 탈출구가 없다. 또, 감옥 내부에는 빈 칸이 적어도 하나 있다.

입력

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

출력

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

예제 입력 1

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

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjE4ODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1MDRcdWI5YWNcdWM5OGMgXHViZTBjXHViODA4XHVjNzc0XHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5OKk0gXHVkMDZjXHVhZTMwXHVjNzU4IFx1YWMxMFx1YzYyNVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWMxMFx1YzYyNVx1Yzc0MCBcdWMyYTRcdWNmNTRcdWQ1NDRcdWI0ZGNcdWFjMDAgXHViYmY4XHViOWFjIFx1YjZhYlx1YzViNCBcdWIxOTNcdWM3NDAgXHVkMGM4XHVjZDljXHVhZDZjLCBcdWJjYmQsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWJlNDggXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTRcdWIzNzAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJlNDggXHVjZTc4XHVjNWQwXHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWQ1NWMgXHViYTg1XHVjNTI5IFx1Yzc4OFx1YjJlNC4gXHVhYzEwXHVjNjI1IFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWQwYzhcdWNkOWNcdWFkNmNcdWI5N2MgXHVkMWI1XHVkNTc0IFx1ZDBjOFx1YzYyNVx1Yzc0NCBcdWQ1NzQgXHViMGI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViYjNjXHViODYwLCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViZTY4XHViOWFjIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkMGM4XHVjZDljXHVkNTU4XHViM2M0XHViODVkIFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkNTVjIFx1Y2U3OFx1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViMzcwXHVjNWQwXHViMjk0IDFcdWNkMDhcdWFjMDAgXHVhYzc4XHViOWFjXHViYTcwLCBcdWQ1NThcdWIwOThcdWM3NTggXHVkMGM4XHVjZDljXHVhZDZjXHViOTdjIFx1ZDFiNVx1ZDU3NFx1YzExY1x1YjI5NCAxXHVjZDA4XHVjNWQwIFx1ZDU1YyBcdWMwYWNcdWI3OGNcdWI5Y2MgXHVkMGM4XHVjZDljXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1ZDBjOFx1Y2Q5Y1x1ZDU1OFx1YjI5NCBcdWIzZDlcdWM1NDhcdWM1ZDBcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YmU0OCBcdWNlNzhcdWM1ZDAgXHVjNWVjXHViN2VjIFx1YmE4NVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjNzg4XHVjNWI0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHVhYzEwXHVjNjI1XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWQwYzhcdWNkOWNcdWQ1NThcdWI4MjRcdWJhNzQgXHViYWE4XHViNDUwIFx1YmE4NyBcdWNkMDhcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjlhY1x1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVhYzEwXHVjNjI1XHVjNzU4IFx1YWMwMFx1YzdhNVx1Yzc5MFx1YjlhY1x1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHViY2JkIFx1YjYxMFx1YjI5NCBcdWQwYzhcdWNkOWNcdWFkNmNcdWM3NzRcdWJhNzAsIFx1YzU0OFx1Y2FiZFx1YzVkMFx1YjI5NCBcdWQwYzhcdWNkOWNcdWFkNmNcdWFjMDAgXHVjNWM2XHViMmU0LiBcdWI2MTAsIFx1YWMxMFx1YzYyNSBcdWIwYjRcdWJkODBcdWM1ZDBcdWIyOTQgXHViZTQ4IFx1Y2U3OFx1Yzc3NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzEwXHVjNjI1XHVjNzU4IFx1ZDU4OVx1Yzc1OCBcdWMyMThcdWM2NDAgXHVjNWY0XHVjNzU4IFx1YzIxOCwgTiwgTVx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQoIDMgJmxlOyBOLE0gJmxlOyAxMiApLiBcdWFkZjhcdWI5YWNcdWFjZTAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YWMxMFx1YzYyNVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAmbHNxdW87WCYjMzk7XHViMjk0IFx1YmNiZFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAgJiMzOTsuJiMzOTtcdWM3NDAgXHViZTQ4IFx1Y2U3OCwgJiMzOTtEJiMzOTtcdWIyOTQgXHVjMmE0XHVjZjU0XHVkNTQ0XHViNGRjXHVhYzAwIFx1YmJmOFx1YjlhYyBcdWI2YWJcdWM1YjQgXHViMTkzXHVjNzQwIFx1ZDBjOFx1Y2Q5Y1x1YWQ2YyBcdWM3MDRcdWNlNThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWQwYzhcdWNkOWNcdWM3NDQgXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZFx1YzVkMCBcdWJhYThcdWI0NTAgXHVkMGM4XHVjZDljXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQgJmxkcXVvO2ltcG9zc2libGUmcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4ODYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFdmFjdWF0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5GaXJlcyBjYW4gYmUgZGlzYXN0cm91cywgZXNwZWNpYWxseSB3aGVuIGEgZmlyZSBicmVha3Mgb3V0IGluIGEgcm9vbSB0aGF0IGlzIGNvbXBsZXRlbHkgZmlsbGVkIHdpdGggcGVvcGxlLiBSb29tcyB1c3VhbGx5IGhhdmUgYSBjb3VwbGUgb2YgZXhpdHMgYW5kIGVtZXJnZW5jeSBleGl0cywgYnV0IHdpdGggZXZlcnlvbmUgcnVzaGluZyBvdXQgYXQgdGhlIHNhbWUgdGltZSwgaXQgbWF5IHRha2UgYSB3aGlsZSBmb3IgZXZlcnlvbmUgdG8gZXNjYXBlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuIHRoZSBmbG9vcnBsYW4gb2YgYSByb29tIGFuZCBtdXN0IGZpbmQgb3V0IGhvdyBtdWNoIHRpbWUgaXQgd2lsbCB0YWtlIGZvciBldmVyeW9uZSB0byBnZXQgb3V0LiBSb29tcyBjb25zaXN0IG9mIG9ic3RhY2xlcyBhbmQgd2FsbHMsIHdoaWNoIGFyZSByZXByZXNlbnRlZCBvbiB0aGUgbWFwIGJ5IGFuICYjMzk7WCYjMzk7LCBlbXB0eSBzcXVhcmVzLCByZXByZXNlbnRlZCBieSBhICYjMzk7LiYjMzk7IGFuZCBleGl0IGRvb3JzLCB3aGljaCBhcmUgcmVwcmVzZW50ZWQgYnkgYSAmIzM5O0QmIzM5Oy4gVGhlIGJvdW5kYXJ5IG9mIHRoZSByb29tIGNvbnNpc3RzIG9ubHkgb2YgZG9vcnMgYW5kIHdhbGxzLCBhbmQgdGhlcmUgYXJlIG5vIGRvb3JzIGluc2lkZSB0aGUgcm9vbS4gVGhlIGludGVyaW9yIG9mIHRoZSByb29tIGNvbnRhaW5zIGF0IGxlYXN0IG9uZSBlbXB0eSBzcXVhcmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluaXRpYWxseSwgdGhlcmUgaXMgb25lIHBlcnNvbiBvbiBldmVyeSBlbXB0eSBzcXVhcmUgaW4gdGhlIHJvb20gYW5kIHRoZXNlIHBlcnNvbnMgc2hvdWxkIG1vdmUgdG8gYSBkb29yIHRvIGV4aXQuIFRoZXkgY2FuIG1vdmUgb25lIHNxdWFyZSBwZXIgc2Vjb25kIHRvIHRoZSBOb3J0aCwgU291dGgsIEVhc3Qgb3IgV2VzdC4gV2hpbGUgZXZhY3VhdGluZywgbXVsdGlwbGUgcGVyc29ucyBjYW4gYmUgb24gYSBzaW5nbGUgc3F1YXJlLiBUaGUgZG9vcnMgYXJlIG5hcnJvdywgaG93ZXZlciwgYW5kIG9ubHkgb25lIHBlcnNvbiBjYW4gbGVhdmUgdGhyb3VnaCBhIGRvb3IgcGVyIHNlY29uZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2hhdCBpcyB0aGUgbWluaW1hbCB0aW1lIG5lY2Vzc2FyeSB0byBldmFjdWF0ZSBldmVyeWJvZHk/IEEgcGVyc29uIGlzIGV2YWN1YXRlZCBhdCB0aGUgbW9tZW50IGhlIG9yIHNoZSBlbnRlcnMgYSBkb29yIHNxdWFyZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0byBmb2xsb3cuIEVhY2ggdGVzdCBjYXNlIGhhcyB0aGUgZm9sbG93aW5nIGZvcm1hdDombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBZIGFuZCBYLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIHNhdGlzZnlpbmcgMyAmbGU7IFksIFggJmxlOyAxMjogdGhlIHNpemUgb2YgdGhlIHJvb20mbmJzcDs8XC9saT5cclxuXHQ8bGk+WSBsaW5lcyB3aXRoIFggY2hhcmFjdGVycywgZWFjaCBjaGFyYWN0ZXIgYmVpbmcgZWl0aGVyICYjMzk7WCYjMzk7LCAmIzM5Oy4mIzM5Oywgb3IgJiMzOTtEJiMzOTs6IGEgdmFsaWQgZGVzY3JpcHRpb24gb2YgYSByb29tPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZXZlcnkgdGVzdCBjYXNlIGluIHRoZSBpbnB1dCwgdGhlIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBsaW5lIHdpdGggdGhlIG1pbmltYWwgZXZhY3VhdGlvbiB0aW1lIGluIHNlY29uZHMsIGlmIGV2YWN1YXRpb24gaXMgcG9zc2libGUsIG9yICZxdW90O2ltcG9zc2libGUmcXVvdDssIGlmIGl0IGlzIG5vdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d