{"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 \u003cp\u003eYou are trapped in a building consisting of open spaces and\n walls. Some places are on fire and you have to run for the\n exit. Will you make it?\u003c/p\u003e\n\n \u003cp\u003eAt each second, the fire will spread to all open spaces\n directly connected to the North, South, East or West side of\n it. Fortunately, walls will never catch fire and will keep the\n fire inside the building, so as soon as you are out of the\n building you will be safe. To run to any of the four open\n spaces adjacent to you takes you exactly one second. You cannot\n run through a wall or into an open space that is on fire or is\n just catching fire, but you can run out of an open space at the\n same moment it catches fire.\u003c/p\u003e\n\n \u003cp\u003eGiven a map of the building, decide how fast you can exit\n the building.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eOn the first line one positive number: the number of test\n cases, at most 100. After that per test case:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eone line with two space-separated integers \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$h$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$(1\\le w, h \\le 1\\, 000)$\u003c/span\u003e: the\n width and height of the map of the building,\n respectively.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$h$\u003c/span\u003e lines with\n \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e characters each:\n the map of the building, consisting of\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003e‘\u003ctt\u003e.\u003c/tt\u003e’: a room,\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e‘\u003ctt\u003e#\u003c/tt\u003e’: a wall,\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e‘\u003ctt\u003e@\u003c/tt\u003e’: your starting location,\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e‘\u003ctt\u003e*\u003c/tt\u003e’: fire.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eThere will be exactly one ‘\u003ctt\u003e@\u003c/tt\u003e’ in the map.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003ePer test case:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eone line with a single integer which is the minimal\n number of seconds that you need to exit the building or the\n string “\u003ctt\u003eIMPOSSIBLE\u003c/tt\u003e” when this is not possible.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\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\u003e5\n4 3\n####\n#*@.\n####\n7 6\n###.###\n#*#.#*#\n#.....#\n#.....#\n#..@..#\n#######\n7 4\n###.###\n#....*#\n#@....#\n.######\n5 5\n.....\n.***.\n.*@*.\n.***.\n.....\n3 3\n###\n#@#\n###\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n5\nIMPOSSIBLE\nIMPOSSIBLE\nIMPOSSIBLE\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}