{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:20.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/2767c90146979a1a6c624a9cfd24fee6?v\u003d1713689533\" alt\u003d\"/problems/fire3/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eJoe works in a maze. Unfortunately, portions of the maze\n have caught on fire, and the owner of the maze neglected to\n create a fire escape plan. Help Joe escape the maze.\u003c/p\u003e\n\n \u003cp\u003eGiven Joe’s location in the maze and which squares of the\n maze are on fire, you must determine whether Joe can exit the\n maze before the fire reaches him, and how fast he can do\n it.\u003c/p\u003e\n\n \u003cp\u003eJoe and the fire each move one square per minute, vertically\n or horizontally (not diagonally). The fire spreads all four\n directions from each square that is on fire. Joe may exit the\n maze from any square that borders the edge of the maze. Neither\n Joe nor the fire may enter a square that is occupied by a\n wall.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line of input contains the two integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$R$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$C$\u003c/span\u003e, separated by spaces, with\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le R, C \\le 1000$\u003c/span\u003e. The\n following \u003cspan class\u003d\"tex2jax_process\"\u003e$R$\u003c/span\u003e lines of\n input each contain one row of the maze. Each of these lines\n contains exactly \u003cspan class\u003d\"tex2jax_process\"\u003e$C$\u003c/span\u003e\n characters, and each of these characters is one of:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003e#\u003c/tt\u003e, a wall\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003e.\u003c/tt\u003e, a passable square\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eJ\u003c/tt\u003e, Joe’s initial position in\n the maze, which is a passable square\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eF\u003c/tt\u003e, a square that is on\n fire\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eThere will be exactly one \u003ctt class\u003d\"ttfamily\"\u003eJ\u003c/tt\u003e in the\n input.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput a single line containing “\u003ctt class\u003d\"ttfamily\"\u003eIMPOSSIBLE\u003c/tt\u003e” if Joe cannot exit the maze before\n the fire reaches him, or an integer giving the earliest time\n Joe can safely exit the maze, in minutes.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 4\n####\n#JF#\n#..#\n#..#\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\n###\n#J.\n#.F\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eIMPOSSIBLE\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}