爆破行动
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
题目背景
小明被困在一座复杂的地下迷宫中，迷宫的结构可以看作一个 R × C 的网格。
迷宫中充满了坚硬的墙壁，但幸运的是，小明手中有一批高能炸药。
题目描述
迷宫由以下字符组成：
“.”：空地，可以直接通过，耗时 0 秒，消耗 0 个炸弹。
“#”：墙壁，阻挡去路。若要通过，必须使用 1 个炸弹将其炸开，耗时（假设为移动耗时，实际只计算炸弹数）视为消耗 1 个代价。
“S”：起点。
“E”：终点。
小明可以向上下左右四个方向移动。
他身上携带的炸弹数量有限，最多只能使用 K 个炸弹。
请你计算：在炸弹使用数量不超过 K 的前提下，从起点 S 到达终点 E，最少需要消耗多少个炸弹？
如果无法在 K 个炸弹内到达，请输出 -1。
输入格式
第一行包含三个整数 R、C、K，分别表示迷宫的行数、列数和最大炸弹携带量。
接下来 R 行，每行包含 C 个字符，表示迷宫的地图。
输出格式
输出一个整数：
如果能到达，输出最少需要的炸弹数量。
如果不能到达或最少数量超过 K，输出 -1。
样例输入
4 5 2
S###.
..##.
#.###
..#.E
样例输出
2
解释：
虽然全是墙，但可以选择 S → 下 → 下 → 右 … 的路线，只炸开少量的墙。
数据范围
1 ≤ R, C ≤ 1000
0 ≤ K ≤ R × C