시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1554 351 249 23.424%

문제

지훈이는 미로에서 일을 한다. 불행히도, 미로의 일부가 불에 붙었고 미로 주인은 게을러서 비상대피로를 만들지 않았다.

지훈이를 미로에서 탈출하도록 도와주자!

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

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

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

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

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

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1<= R,C <= 1000

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

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

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

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

출력

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

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

예제 입력 1

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

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjQxNzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODghIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWQ2YzhcdWM3NzRcdWIyOTQgXHViYmY4XHViODVjXHVjNWQwXHVjMTFjIFx1Yzc3Y1x1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YmQ4OFx1ZDU4OVx1ZDc4OFx1YjNjNCwgXHViYmY4XHViODVjXHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1YWMwMCBcdWJkODhcdWM1ZDAgXHViZDk5XHVjNWM4XHVhY2UwIFx1YmJmOFx1Yjg1YyBcdWM4ZmNcdWM3NzhcdWM3NDAgXHVhYzhjXHVjNzQ0XHViN2VjXHVjMTFjIFx1YmU0NFx1YzBjMVx1YjMwMFx1ZDUzY1x1Yjg1Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWQ2YzhcdWM3NzRcdWI5N2MgXHViYmY4XHViODVjXHVjNWQwXHVjMTFjIFx1ZDBjOFx1Y2Q5Y1x1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWIzYzRcdWM2NDBcdWM4ZmNcdWM3OTAhPFwvcD5cclxuXHJcbjxwPlx1YmJmOFx1Yjg1Y1x1YzVkMFx1YzExY1x1Yzc1OCBcdWM5YzBcdWQ2YzhcdWM3NzRcdWM3NTggXHVjNzA0XHVjZTU4XHVjNjQwIFx1YmQ4OFx1Yzc3NCBcdWJkOTlcdWM3NDAgXHVjNzA0XHVjZTU4XHViOTdjIFx1YWMxMFx1YzU0OFx1ZDU3NFx1YzExYyBcdWM5YzBcdWQ2YzhcdWM3NzRcdWFjMDAgXHViZDg4XHVjNWQwIFx1ZDBjMFx1YWUzMFx1YzgwNFx1YzVkMCBcdWQwYzhcdWNkOWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMFx1Yzc1OCBcdWM1ZWNcdWJkODAsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM1YmNcdWI5YzhcdWIwOTggXHViZTY4XHViOWFjIFx1ZDBjOFx1Y2Q5Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1YWNiMFx1YzgxNVx1ZDU3NFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWMwXHVkNmM4XHVjNzc0XHVjNjQwIFx1YmQ4OFx1Yzc0MCBcdWI5ZTQgXHViZDg0XHViOWM4XHViMmU0IFx1ZDU1Y1x1Y2U3OFx1YzUyOSBcdWMyMThcdWQzYzlcdWI2MTBcdWIyOTQgXHVjMjE4XHVjOWMxXHVjNzNjXHViODVjKFx1YmU0NFx1YzJhNFx1YjRlY1x1ZDU1OFx1YWM4YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0KSZuYnNwOyBcdWM3NzRcdWIzZDlcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YmQ4OFx1Yzc0MCBcdWFjMDEgXHVjOWMwXHVjODEwXHVjNWQwXHVjMTFjIFx1YjEyNCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVkNjU1XHVjMGIwXHViNDFjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWQ2YzhcdWM3NzRcdWIyOTQgXHViYmY4XHViODVjXHVjNzU4IFx1YWMwMFx1YzdhNVx1Yzc5MFx1YjlhY1x1YzVkMCBcdWM4MTFcdWQ1NWMgXHVhY2Y1XHVhYzA0XHVjNWQwXHVjMTFjIFx1ZDBjOFx1Y2Q5Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWQ2YzhcdWM3NzRcdWM2NDAgXHViZDg4XHVjNzQwIFx1YmNiZFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhY2Y1XHVhYzA0XHVjNzQwIFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDFjIFx1YjQ1MCBcdWM4MTVcdWMyMTggUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU4LCAxJmx0Oz0gUixDICZsdDs9IDEwMDA8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBSXHVjOTA0XHViM2Q5XHVjNTQ4IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJiZjhcdWI4NWMgXHVkNTg5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7XHVhYzAxXHVhYzAxXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWM3NDQgXHViNzNiXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiM6IFx1YmNiZDxcL2xpPlxyXG5cdDxsaT4uOiBcdWM5YzBcdWIwOThcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjZjVcdWFjMDQ8XC9saT5cclxuXHQ8bGk+SjogXHVjOWMwXHVkNmM4XHVjNzc0XHVjNzU4IFx1YmJmOFx1Yjg1Y1x1YzVkMFx1YzExY1x1Yzc1OCBcdWNkMDhcdWFlMzBcdWM3MDRcdWNlNTggKFx1YzljMFx1YjA5OFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNmNVx1YWMwNCk8XC9saT5cclxuXHQ8bGk+RjogXHViZDg4XHVjNzc0XHViMDljIFx1YWNmNVx1YWMwNDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkpcdWIyOTQgXHVjNzg1XHViODI1XHVjNWQwXHVjMTFjIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOWMwXHVkNmM4XHVjNzc0XHVhYzAwIFx1YmQ4OFx1Yzc3NCBcdWIzYzRcdWIyZWNcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1YmJmOFx1Yjg1Y1x1Yjk3YyBcdWQwYzhcdWNkOWMgXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTRcdWFjYmRcdWM2YjAgSU1QT1NTSUJMRSBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWQ2YzhcdWM3NzRcdWFjMDAgXHViYmY4XHViODVjXHViOTdjIFx1ZDBjOFx1Y2Q5Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVkMGM4XHVjZDljXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MTc5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmlyZSEiLCJkZXNjcmlwdGlvbiI6IjxwPkpvZSB3b3JrcyBpbiBhIG1hemUuIFVuZm9ydHVuYXRlbHksIHBvcnRpb25zIG9mIHRoZSBtYXplIGhhdmUgY2F1Z2h0IG9uIGZpcmUsIGFuZCB0aGUgb3duZXIgb2YgdGhlIG1hemUgbmVnbGVjdGVkIHRvIGNyZWF0ZSBhIGZpcmUgZXNjYXBlIHBsYW4uIEhlbHAgSm9lIGVzY2FwZSB0aGUgbWF6ZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gSm9lJiMzOTtzIGxvY2F0aW9uIGluIHRoZSBtYXplIGFuZCB3aGljaCBzcXVhcmVzIG9mIHRoZSBtYXplIGFyZSBvbiBmaXJlLCB5b3UgbXVzdCBkZXRlcm1pbmUgd2hldGhlciBKb2UgY2FuIGV4aXQgdGhlIG1hemUgYmVmb3JlIHRoZSBmaXJlIHJlYWNoZXMgaGltLCBhbmQgaG93IGZhc3QgaGUgY2FuIGRvIGl0LjxcL3A+XHJcblxyXG48cD5Kb2UgYW5kIHRoZSBmaXJlIGVhY2ggbW92ZSBvbmUgc3F1YXJlIHBlciBtaW51dGUsIHZlcnRpY2FsbHkgb3IgaG9yaXpvbnRhbGx5IChub3QgZGlhZ29uYWxseSkuIFRoZSBmaXJlIHNwcmVhZHMgYWxsIGZvdXIgZGlyZWN0aW9ucyBmcm9tIGVhY2ggc3F1YXJlIHRoYXQgaXMgb24gZmlyZS4gSm9lIG1heSBleGl0IHRoZSBtYXplIGZyb20gYW55IHNxdWFyZSB0aGF0IGJvcmRlcnMgdGhlIGVkZ2Ugb2YgdGhlIG1hemUuIE5laXRoZXIgSm9lIG5vciB0aGUgZmlyZSBtYXkgZW50ZXIgYSBzcXVhcmUgdGhhdCBpcyBvY2N1cGllZCBieSBhIHdhbGwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgdHdvIGludGVnZXJzIFIgYW5kIEMsIHNlcGFyYXRlZCBieSBzcGFjZXMsIHdpdGggMSAmbHQ7PSBSLEMgJmx0Oz0gMTAwMC4gVGhlIGZvbGxvd2luZyBSIGxpbmVzIG9mIGlucHV0IGVhY2ggY29udGFpbiBvbmUgcm93IG9mIHRoZSBtYXplLiBFYWNoIG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zIGV4YWN0bHkgQyBjaGFyYWN0ZXJzLCBhbmQgZWFjaCBvZiB0aGVzZSBjaGFyYWN0ZXJzIGlzIG9uZSBvZjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4jLCBhIHdhbGw8XC9saT5cclxuXHQ8bGk+LiwgYSBwYXNzYWJsZSBzcXVhcmU8XC9saT5cclxuXHQ8bGk+SiwgSm9lJiMzOTtzIGluaXRpYWwgcG9zaXRpb24gaW4gdGhlIG1hemUsIHdoaWNoIGlzIGEgcGFzc2FibGUgc3F1YXJlPFwvbGk+XHJcblx0PGxpPkYsIGEgc3F1YXJlIHRoYXQgaXMgb24gZmlyZTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZXJlIHdpbGwgYmUgZXhhY3RseSBvbmUgSiBpbiB0aGUgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBJTVBPU1NJQkxFIGlmIEpvZSBjYW5ub3QgZXhpdCB0aGUgbWF6ZSBiZWZvcmUgdGhlIGZpcmUgcmVhY2hlcyBoaW0sIG9yIGFuIGludGVnZXIgZ2l2aW5nIHRoZSBlYXJsaWVzdCB0aW1lIEpvZSBjYW4gc2FmZWx5IGV4aXQgdGhlIG1hemUsIGluIG1pbnV0ZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 잘못된 번역을 찾은 사람: jh05013
  • 문제를 번역한 사람: lyzqm