#LX0008. 营救【2024五一模拟赛】

营救【2024五一模拟赛】

题目描述

BobBob 梦想成真,当了一名消防员。今天接到一项“营救”任务,在一个 h×wh \times w 网格的区域营救 num(num=1,2)num(num=1,2) 个人。

网格区域是由 '.' , '#' , '*' 构成的,共 hhww 列,需要营救的人的位置是 '$'。

其中: '.' 表示空格,可以自由走动。'#' 是门,但需要暴力破门。'*' 是墙,无法通过。'$' 表示要营救的人,当然营救的位置没有门,也没有墙。

网格区域四周都可以自由进入,'.' 是空格,可以自由出入的,'#' 的位置需要暴力破门,BobBob 的想知道至少需要暴力打开几扇门才能将 其中 numnum 个人全部救出,当然此次营救任务比较简单,num=1num =122. (门暴力打来一次后,门就永久打开了)

当然如果无法完成营救任务,也就是无法将 numnum 个人全部救出,输出 "impossible"

输入格式

第一行,两个整数 hhww

接下来 hh 行,每行 ww 个字符(由‘.’,‘#’,‘*’,‘$’)构成。

输出格式

一个整数,表示将全部人营救出来,需要最少暴力破门的次数。

5 5
##*##
#####
##$#*
#####
##.##
1
5 5
##*##
##*##
#*$**
##*##
##.##
impossible
5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********
4
5 9
****#****
*..#.#..*
****.****
*$#.#.*$*
*********
impossible
5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*
0
9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********
9

样例6解释

营救路线如下图:

image

数据规模与约定

subtask1:1h,w100,num=1subtask1 : 1\leq h,w \leq 100,num=1 , 5050分;

subtask2:1h,w100,num{1,2}subtask2: 1\leq h,w \leq 100, num \in \{1,2 \} , 5050分;