T485253 小迪的艺术

小迪被困在了 $n*m$ 的迷宫中，小迪想用爆炸炸掉障碍以离开迷宫，然而小迪的起爆黏土有时并不能炸开所有的障碍物（每个单位的黏土可以炸毁一格障碍物），小迪十分苦恼。由于小迪脑子转得很慢，所有请你算出小迪脱离迷宫最少需要多少个单位的起爆黏土(而且不能炸到小迪)。

第 $1$ 行： 两个变量n，m(表示粘土炸弹所能炸的范围)。 第$ 2$ ~ $n+1$ 行：每行m个字符，表示迷宫地形，"#"表示障碍物，"."表示空地，"*"表示小迪的位置 第 $n+2$ 行：两个整数 $x,y$ 表示迷宫出口。

一个数：最少需要的起爆黏土

对于 $100$% 的数据，$n,m \le 30$。