P10233: 爆炸
传统题
1.000s
时间限制
64MB
内存限制
4 提交
2 解决
【题目描述】
给你一个n行m列的点阵，“#”代表墙，“．”代表空地，“B”代表出发点，“E”代表出口，你从出发点开始，每一步可以走到上、下、左、右四个方向的相邻空地，问你至少要走多少秒才能走到出口？你的步伐很一致，走一步耗时1秒。这个问题太简单了，加点难度：你身上带有k个炸弹，一个炸弹可以把一堵墙炸为空地，但墙要2秒后才能变为空地。也就是说，假如现在是时刻t，你在某格子放了一个炸弹，那么该格子在时刻t+l变成空地，你最早在时刻t+2才能进入该格子。注意：你每次只能把炸弹放在你所在的当前位置的相邻的四个格子，一个炸弹只能炸一堵墙。 有了k个炸弹，你从出发点到终点最少要耗时几秒？如果无法到达，输出-1。
【输入】
第1行：三个整数n，m'k，l≤n，m≤50,0≤k≤100。接下来是n行m列的点阵，“#”，代表墙，“.”代表空地，“B”代表出发点，“E”代表出口。
【输出】
一个整数，有了k个炸弹，你从出发点到终点最少要耗时几秒？如果无法到达，输出一1。
【样例输入】复制
6 7 1
.....B.
.#####.
.#...#.
.#E#.#.
.###.#.
.......
【提示】
第1秒：向左走，到达点(1，5)；
第2秒：在点(2，5)处放一个炸弹；
第3秒：点(2，5)的墙变成空地；
第4秒：向下走，进入点(2，5)；
第5秒：向下走，进入点(3，5)；
第6秒：向左走，进入点(3，4)；
第7秒：向左走，进入点(3，3)；
第8秒：向下走，到达终点(4，3)。