问题 1269. -- The Binding Of Issac

1269: The Binding Of Issac

时间限制: 1 Sec  内存限制: 128 MB
提交: 45  解决: 15
[提交][状态][讨论版]

题目描述

williamchen 每天就知道玩游戏，他最喜欢玩 The Binding Of Issac。

有时候他会进入一个充满石头的房间，有时候他需要控制以撒从这个房间的某个位置走到另一个位置。

为了简化问题，一个房间被抽象成一个二维矩阵(10*10)，由下列符号组成。

S : 代表以撒现在所处的位置，地图中只会出现一个。

r : 代表地图中的石头，不能通过。

* : 代表地图中的空地，可以通过。

E : 代表以撒想要去的目标位置，地图上只能出现一个。

B : 代表炸弹，地图中只会出现一个。

以撒不能通过石头，也不能站在石头上，他每一秒中只能向上下左右四个方向之一移动一个距离。

炸弹的作用是，可以将上下左右的四块石头（如果有）全部清除，炸弹只能被放置在空地上。以撒现在没有炸弹，他可能需要去捡一个炸弹帮助他到达目的地或是让他更快地到达目的地。捡这个炸弹或者放置炸弹都是不用耗费时间的。

以撒只能在自己的脚下放置炸弹，因为他已经捡到防爆道具，所以不需要担心是否炸伤自己。请问以撒最快用几秒能到达目的地，如果不能到达，请输出-1。

输入

包含一个 10 * 10 的二维矩阵。

输出

输出一个数，代表到达目的地的最短时间，或是-1 代表不能到达目的地。

样例输入

**********
**********
**********
**********
**********
**********
**********
**********
rrrrrr****
****ErS**B

样例输出

8

提示

样例解释：


以撒先向右走三格捡到一个炸弹。再向左走三格，放置炸弹。爆炸完成后，再向左走两格，到达目的地。一共耗费时间为 8 秒。



炸弹的使用必然是一次性的。



以撒不一定必须捡炸弹。

来源

2017-freshmen-onsite

[提交][状态][讨论版]