시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2006 449 315 22.452%

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

  • #: 벽
  • .: 지나갈 수 있는 공간
  • J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
  • F: 불이난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

예제 입력 1

4 4
####
#JF#
#..#
#..#

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjQxNzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODghIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWQ2YzhcdWM3NzRcdWIyOTQgXHViYmY4XHViODVjXHVjNWQwXHVjMTFjIFx1Yzc3Y1x1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YzljMFx1ZDZjOFx1Yzc3NFx1Yjk3YyBcdWJiZjhcdWI4NWNcdWM1ZDBcdWMxMWMgXHVkMGM4XHVjZDljXHVkNTU4XHViM2M0XHViODVkIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MCE8XC9wPlxyXG5cclxuPHA+XHViYmY4XHViODVjXHVjNWQwXHVjMTFjXHVjNzU4IFx1YzljMFx1ZDZjOFx1Yzc3NFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM2NDAgXHViZDg4XHVjNzc0IFx1YmQ5OVx1Yzc0MCBcdWM3MDRcdWNlNThcdWI5N2MgXHVhYzEwXHVjNTQ4XHVkNTc0XHVjMTFjIFx1YzljMFx1ZDZjOFx1Yzc3NFx1YWMwMCBcdWJkODhcdWM1ZDAgXHVkMGMwXHVhZTMwXHVjODA0XHVjNWQwIFx1ZDBjOFx1Y2Q5Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHVjNzU4IFx1YzVlY1x1YmQ4MCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1YzViY1x1YjljOFx1YjA5OCBcdWJlNjhcdWI5YWMgXHVkMGM4XHVjZDljXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzBcdWI5N2MgXHVhY2IwXHVjODE1XHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWQ2YzhcdWM3NzRcdWM2NDAgXHViZDg4XHVjNzQwIFx1YjllNCBcdWJkODRcdWI5YzhcdWIyZTQgXHVkNTVjXHVjZTc4XHVjNTI5IFx1YzIxOFx1ZDNjOVx1YjYxMFx1YjI5NCBcdWMyMThcdWM5YzFcdWM3M2NcdWI4NWMoXHViZTQ0XHVjMmE0XHViNGVjXHVkNTU4XHVhYzhjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpJm5ic3A7IFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViZDg4XHVjNzQwIFx1YWMwMSBcdWM5YzBcdWM4MTBcdWM1ZDBcdWMxMWMgXHViMTI0IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWQ2NTVcdWMwYjBcdWI0MWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzljMFx1ZDZjOFx1Yzc3NFx1YjI5NCBcdWJiZjhcdWI4NWNcdWM3NTggXHVhYzAwXHVjN2E1XHVjNzkwXHViOWFjXHVjNWQwIFx1YzgxMVx1ZDU1YyBcdWFjZjVcdWFjMDRcdWM1ZDBcdWMxMWMgXHVkMGM4XHVjZDljXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzljMFx1ZDZjOFx1Yzc3NFx1YzY0MCBcdWJkODhcdWM3NDAgXHViY2JkXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjZjVcdWFjMDRcdWM3NDAgXHVkMWI1XHVhY2ZjXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MWMgXHViNDUwIFx1YzgxNVx1YzIxOCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTgsIDEgJmxlOyBSLCBDICZsZTsgMTAwMCBcdWM3NzRcdWIyZTQuIFJcdWM3NDAgXHViYmY4XHViODVjIFx1ZDU4OVx1Yzc1OCBcdWFjMWNcdWMyMTgsIENcdWIyOTQgXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBSXHVjOTA0XHViM2Q5XHVjNTQ4IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJiZjhcdWI4NWMgXHVkNTg5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7XHVhYzAxXHVhYzAxXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWM3NDQgXHViNzNiXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiM6IFx1YmNiZDxcL2xpPlxyXG5cdDxsaT4uOiBcdWM5YzBcdWIwOThcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjZjVcdWFjMDQ8XC9saT5cclxuXHQ8bGk+SjogXHVjOWMwXHVkNmM4XHVjNzc0XHVjNzU4IFx1YmJmOFx1Yjg1Y1x1YzVkMFx1YzExY1x1Yzc1OCBcdWNkMDhcdWFlMzBcdWM3MDRcdWNlNTggKFx1YzljMFx1YjA5OFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNmNVx1YWMwNCk8XC9saT5cclxuXHQ8bGk+RjogXHViZDg4XHVjNzc0XHViMDljIFx1YWNmNVx1YWMwNDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkpcdWIyOTQgXHVjNzg1XHViODI1XHVjNWQwXHVjMTFjIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOWMwXHVkNmM4XHVjNzc0XHVhYzAwIFx1YmQ4OFx1Yzc3NCBcdWIzYzRcdWIyZWNcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1YmJmOFx1Yjg1Y1x1Yjk3YyBcdWQwYzhcdWNkOWMgXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTRcdWFjYmRcdWM2YjAgSU1QT1NTSUJMRSBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWQ2YzhcdWM3NzRcdWFjMDAgXHViYmY4XHViODVjXHViOTdjIFx1ZDBjOFx1Y2Q5Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1ZDBjOFx1Y2Q5Y1x1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDE3OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpcmUhIiwiZGVzY3JpcHRpb24iOiI8cD5Kb2Ugd29ya3MgaW4gYSBtYXplLiBVbmZvcnR1bmF0ZWx5LCBwb3J0aW9ucyBvZiB0aGUgbWF6ZSBoYXZlIGNhdWdodCBvbiBmaXJlLCBhbmQgdGhlIG93bmVyIG9mIHRoZSBtYXplIG5lZ2xlY3RlZCB0byBjcmVhdGUgYSBmaXJlIGVzY2FwZSBwbGFuLiBIZWxwIEpvZSBlc2NhcGUgdGhlIG1hemUuPFwvcD5cclxuXHJcbjxwPkdpdmVuIEpvZSYjMzk7cyBsb2NhdGlvbiBpbiB0aGUgbWF6ZSBhbmQgd2hpY2ggc3F1YXJlcyBvZiB0aGUgbWF6ZSBhcmUgb24gZmlyZSwgeW91IG11c3QgZGV0ZXJtaW5lIHdoZXRoZXIgSm9lIGNhbiBleGl0IHRoZSBtYXplIGJlZm9yZSB0aGUgZmlyZSByZWFjaGVzIGhpbSwgYW5kIGhvdyBmYXN0IGhlIGNhbiBkbyBpdC48XC9wPlxyXG5cclxuPHA+Sm9lIGFuZCB0aGUgZmlyZSBlYWNoIG1vdmUgb25lIHNxdWFyZSBwZXIgbWludXRlLCB2ZXJ0aWNhbGx5IG9yIGhvcml6b250YWxseSAobm90IGRpYWdvbmFsbHkpLiBUaGUgZmlyZSBzcHJlYWRzIGFsbCBmb3VyIGRpcmVjdGlvbnMgZnJvbSBlYWNoIHNxdWFyZSB0aGF0IGlzIG9uIGZpcmUuIEpvZSBtYXkgZXhpdCB0aGUgbWF6ZSBmcm9tIGFueSBzcXVhcmUgdGhhdCBib3JkZXJzIHRoZSBlZGdlIG9mIHRoZSBtYXplLiBOZWl0aGVyIEpvZSBub3IgdGhlIGZpcmUgbWF5IGVudGVyIGEgc3F1YXJlIHRoYXQgaXMgb2NjdXBpZWQgYnkgYSB3YWxsLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHR3byBpbnRlZ2VycyBSIGFuZCBDLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLCB3aXRoIDEgJmx0Oz0gUixDICZsdDs9IDEwMDAuIFRoZSBmb2xsb3dpbmcgUiBsaW5lcyBvZiBpbnB1dCBlYWNoIGNvbnRhaW4gb25lIHJvdyBvZiB0aGUgbWF6ZS4gRWFjaCBvZiB0aGVzZSBsaW5lcyBjb250YWlucyBleGFjdGx5IEMgY2hhcmFjdGVycywgYW5kIGVhY2ggb2YgdGhlc2UgY2hhcmFjdGVycyBpcyBvbmUgb2Y6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+IywgYSB3YWxsPFwvbGk+XHJcblx0PGxpPi4sIGEgcGFzc2FibGUgc3F1YXJlPFwvbGk+XHJcblx0PGxpPkosIEpvZSYjMzk7cyBpbml0aWFsIHBvc2l0aW9uIGluIHRoZSBtYXplLCB3aGljaCBpcyBhIHBhc3NhYmxlIHNxdWFyZTxcL2xpPlxyXG5cdDxsaT5GLCBhIHNxdWFyZSB0aGF0IGlzIG9uIGZpcmU8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGVyZSB3aWxsIGJlIGV4YWN0bHkgb25lIEogaW4gdGhlIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgSU1QT1NTSUJMRSBpZiBKb2UgY2Fubm90IGV4aXQgdGhlIG1hemUgYmVmb3JlIHRoZSBmaXJlIHJlYWNoZXMgaGltLCBvciBhbiBpbnRlZ2VyIGdpdmluZyB0aGUgZWFybGllc3QgdGltZSBKb2UgY2FuIHNhZmVseSBleGl0IHRoZSBtYXplLCBpbiBtaW51dGVzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Waterloo's local Programming Contests > 13 June, 2009 B번