火蔓延的迷宫

测试数据来自 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

网格上的DFS和BFS

未认领
状态
已结束
题目
10
开始时间
2024-05-11 00:00
截止时间
2024-08-03 23:59
可延期
24.0 小时