火蔓延的迷宫
测试数据来自 system/1911
作业已超过截止时间,您无法递交本题目。
时间限制:1秒 内存限制:256M
【题目描述】
你的任务是帮助Joe 走出一个大火蔓延的迷宫。Joe 每分钟可以走到上下左右 4 个方向的相邻格子之一,而所有着火的格子都会四周蔓延(即如果某个空格子与着火格子有公共边,则下一分钟这个空格子将着火)。迷宫中有一些障碍格,Joe 和火都无法进入。当 Joe 走到一个迷宫的边界格子时,我们认为他已经出了迷宫。
【输入格式】
第一行为两个整数 \(R\) 和 \(C\)。
以下 \(R\) 行每行有 \(C\) 个字符,即迷宫,其中“#”表示墙和障碍物,“.”表示空地,“J”是joe的初始位置(也就是空地),"F"是着火格子。每组数据的迷宫中恰好有一个格是"J"。
【输出格式】
如无法走出迷宫,则输出 IMPOSSIBLE,否则输出走出迷宫的最短时间(单位:分钟)。
【输入输出样例1】
Input
4 4
####
#JF#
#..#
#..#
Output
3
【输入输出样例2】
Input
3 3
###
#J.
#.F
Output
IMPOSSIBLE
【数据限制】
对于 \(100\%\) 的数据,\(1≤R,C≤1000\)。
【来源】
Mr.he