#4289. 「2023.03五级」 打怪救公主 暂未评定

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

公主被魔王抓起来关在了迷宫的某处,骑士想要拯救公主,也进入了迷宫。

但是魔王不会轻易让骑士拯救公主,魔王在迷宫中安排了许多怪兽。

每个怪兽都有血量,骑士也有初始血量,骑士打败怪兽后血量的减少量为怪物的血量值,血量减到0,骑士会死去。

迷宫由m*n个方块组成,每个方块有墙或者路或者怪物,骑士在其中一个方块上,他每个时间单位可以四个方向(上、下、左、右)走到相邻方格,若遇到怪物,必须打败怪物才能继续前进。

请帮忙判断骑士能否成功拯救公主,如果能,给出骑士还剩的最大血量。

输入格式

第一行为三个整数m、n和t,t表示骑士的初始血量。(m,n <= 20, t <= 30) 第2至m+1行描述了迷宫,迷宫以m行n列的方格组成,若方格为"."则表示骑士可以通过,若方格为"#"则表示墙,骑士不能通过,若方格为数字则表示怪物,数字为怪物的血量,保证怪物的血量小于10(一位数)。"*"表示了骑士当前所在的位置,"+"表示公主被囚禁的位置。

输出格式

若骑士能成功拯救公主,则输出骑士走到公主所囚禁方格所剩最大血量,否则输出0。

样例

样例输入

5 6 10
..*...
.#2###
5#..4#
.##9.#
.#+..#

样例输出

4