시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB5668212610843820.717%

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

예제 입력 1

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

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjQxNzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODghIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWQ2YzhcdWM3NzRcdWIyOTQgXHViYmY4XHViODVjXHVjNWQwXHVjMTFjIFx1Yzc3Y1x1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YzljMFx1ZDZjOFx1Yzc3NFx1Yjk3YyBcdWJiZjhcdWI4NWNcdWM1ZDBcdWMxMWMgXHVkMGM4XHVjZDljXHVkNTU4XHViM2M0XHViODVkIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MCE8XC9wPlxyXG5cclxuPHA+XHViYmY4XHViODVjXHVjNWQwXHVjMTFjXHVjNzU4IFx1YzljMFx1ZDZjOFx1Yzc3NFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM2NDAgXHViZDg4XHVjNzc0IFx1YmQ5OVx1Yzc0MCBcdWM3MDRcdWNlNThcdWI5N2MgXHVhYzEwXHVjNTQ4XHVkNTc0XHVjMTFjIFx1YzljMFx1ZDZjOFx1Yzc3NFx1YWMwMCBcdWJkODhcdWM1ZDAgXHVkMGMwXHVhZTMwXHVjODA0XHVjNWQwIFx1ZDBjOFx1Y2Q5Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHVjNzU4IFx1YzVlY1x1YmQ4MCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1YzViY1x1YjljOFx1YjA5OCBcdWJlNjhcdWI5YWMgXHVkMGM4XHVjZDljXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzBcdWI5N2MgXHVhY2IwXHVjODE1XHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWQ2YzhcdWM3NzRcdWM2NDAgXHViZDg4XHVjNzQwIFx1YjllNCBcdWJkODRcdWI5YzhcdWIyZTQgXHVkNTVjXHVjZTc4XHVjNTI5IFx1YzIxOFx1ZDNjOVx1YjYxMFx1YjI5NCBcdWMyMThcdWM5YzFcdWM3M2NcdWI4NWMoXHViZTQ0XHVjMmE0XHViNGVjXHVkNTU4XHVhYzhjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpICBcdWM3NzRcdWIzZDlcdWQ1NWNcdWIyZTQuIDxcL3A+XHJcblxyXG48cD5cdWJkODhcdWM3NDAgXHVhYzAxIFx1YzljMFx1YzgxMFx1YzVkMFx1YzExYyBcdWIxMjQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1ZDY1NVx1YzBiMFx1YjQxY1x1YjJlNC4gPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1ZDZjOFx1Yzc3NFx1YjI5NCBcdWJiZjhcdWI4NWNcdWM3NTggXHVhYzAwXHVjN2E1XHVjNzkwXHViOWFjXHVjNWQwIFx1YzgxMVx1ZDU1YyBcdWFjZjVcdWFjMDRcdWM1ZDBcdWMxMWMgXHVkMGM4XHVjZDljXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIDxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWQ2YzhcdWM3NzRcdWM2NDAgXHViZDg4XHVjNzQwIFx1YmNiZFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhY2Y1XHVhYzA0XHVjNzQwIFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDFjIFx1YjQ1MCBcdWM4MTVcdWMyMTggUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU4LCAxICZsZTsgUiwgQyAmbGU7IDEwMDAgXHVjNzc0XHViMmU0LiBSXHVjNzQwIFx1YmJmOFx1Yjg1YyBcdWQ1ODlcdWM3NTggXHVhYzFjXHVjMjE4LCBDXHViMjk0IFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgUlx1YzkwNFx1YjNkOVx1YzU0OCBcdWFjMDFcdWFjMDFcdWM3NTggXHViYmY4XHViODVjIFx1ZDU4OVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiBcdWFjMDFcdWFjMDFcdWM3NTggXHViYjM4XHVjNzkwXHViNGU0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1Yzc0NCBcdWI3M2JcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+IzogXHViY2JkPFwvbGk+XHJcblx0PGxpPi46IFx1YzljMFx1YjA5OFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNmNVx1YWMwNDxcL2xpPlxyXG5cdDxsaT5KOiBcdWM5YzBcdWQ2YzhcdWM3NzRcdWM3NTggXHViYmY4XHViODVjXHVjNWQwXHVjMTFjXHVjNzU4IFx1Y2QwOFx1YWUzMFx1YzcwNFx1Y2U1OCAoXHVjOWMwXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2Y1XHVhYzA0KTxcL2xpPlxyXG5cdDxsaT5GOiBcdWJkODhcdWM3NzQgXHViMDljIFx1YWNmNVx1YWMwNDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkpcdWIyOTQgXHVjNzg1XHViODI1XHVjNWQwXHVjMTFjIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOWMwXHVkNmM4XHVjNzc0XHVhYzAwIFx1YmQ4OFx1Yzc3NCBcdWIzYzRcdWIyZWNcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1YmJmOFx1Yjg1Y1x1Yjk3YyBcdWQwYzhcdWNkOWMgXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwIElNUE9TU0lCTEUgXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWMwXHVkNmM4XHVjNzc0XHVhYzAwIFx1YmJmOFx1Yjg1Y1x1Yjk3YyBcdWQwYzhcdWNkOWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWQwYzhcdWNkOWNcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiA8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI0MTc5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmlyZSEiLCJkZXNjcmlwdGlvbiI6IjxwPkpvZSB3b3JrcyBpbiBhIG1hemUuIFVuZm9ydHVuYXRlbHksIHBvcnRpb25zIG9mIHRoZSBtYXplIGhhdmUgY2F1Z2h0IG9uIGZpcmUsIGFuZCB0aGUgb3duZXIgb2YgdGhlIG1hemUgbmVnbGVjdGVkIHRvIGNyZWF0ZSBhIGZpcmUgZXNjYXBlIHBsYW4uIEhlbHAgSm9lIGVzY2FwZSB0aGUgbWF6ZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gSm9lJiMzOTtzIGxvY2F0aW9uIGluIHRoZSBtYXplIGFuZCB3aGljaCBzcXVhcmVzIG9mIHRoZSBtYXplIGFyZSBvbiBmaXJlLCB5b3UgbXVzdCBkZXRlcm1pbmUgd2hldGhlciBKb2UgY2FuIGV4aXQgdGhlIG1hemUgYmVmb3JlIHRoZSBmaXJlIHJlYWNoZXMgaGltLCBhbmQgaG93IGZhc3QgaGUgY2FuIGRvIGl0LjxcL3A+XHJcblxyXG48cD5Kb2UgYW5kIHRoZSBmaXJlIGVhY2ggbW92ZSBvbmUgc3F1YXJlIHBlciBtaW51dGUsIHZlcnRpY2FsbHkgb3IgaG9yaXpvbnRhbGx5IChub3QgZGlhZ29uYWxseSkuIFRoZSBmaXJlIHNwcmVhZHMgYWxsIGZvdXIgZGlyZWN0aW9ucyBmcm9tIGVhY2ggc3F1YXJlIHRoYXQgaXMgb24gZmlyZS4gSm9lIG1heSBleGl0IHRoZSBtYXplIGZyb20gYW55IHNxdWFyZSB0aGF0IGJvcmRlcnMgdGhlIGVkZ2Ugb2YgdGhlIG1hemUuIE5laXRoZXIgSm9lIG5vciB0aGUgZmlyZSBtYXkgZW50ZXIgYSBzcXVhcmUgdGhhdCBpcyBvY2N1cGllZCBieSBhIHdhbGwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgdHdvIGludGVnZXJzIFIgYW5kIEMsIHNlcGFyYXRlZCBieSBzcGFjZXMsIHdpdGggMSAmbHQ7PSBSLEMgJmx0Oz0gMTAwMC4gVGhlIGZvbGxvd2luZyBSIGxpbmVzIG9mIGlucHV0IGVhY2ggY29udGFpbiBvbmUgcm93IG9mIHRoZSBtYXplLiBFYWNoIG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zIGV4YWN0bHkgQyBjaGFyYWN0ZXJzLCBhbmQgZWFjaCBvZiB0aGVzZSBjaGFyYWN0ZXJzIGlzIG9uZSBvZjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4jLCBhIHdhbGw8XC9saT5cclxuXHQ8bGk+LiwgYSBwYXNzYWJsZSBzcXVhcmU8XC9saT5cclxuXHQ8bGk+SiwgSm9lJiMzOTtzIGluaXRpYWwgcG9zaXRpb24gaW4gdGhlIG1hemUsIHdoaWNoIGlzIGEgcGFzc2FibGUgc3F1YXJlPFwvbGk+XHJcblx0PGxpPkYsIGEgc3F1YXJlIHRoYXQgaXMgb24gZmlyZTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZXJlIHdpbGwgYmUgZXhhY3RseSBvbmUgSiBpbiB0aGUgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBJTVBPU1NJQkxFIGlmIEpvZSBjYW5ub3QgZXhpdCB0aGUgbWF6ZSBiZWZvcmUgdGhlIGZpcmUgcmVhY2hlcyBoaW0sIG9yIGFuIGludGVnZXIgZ2l2aW5nIHRoZSBlYXJsaWVzdCB0aW1lIEpvZSBjYW4gc2FmZWx5IGV4aXQgdGhlIG1hemUsIGluIG1pbnV0ZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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