T44349 逃亡

与此同时，混沌即将笼罩小马国，小马们决定逃离家园。 小马国的一片地形可以抽象成一个$n \times m$的平面网格图。 其中'.'表示平原，'#'表示高山，小马们只能在平原上奔跑。 但是，由于无序的重生，许多的精灵也重新出现在了小马国。

精灵主要分为三种：火精灵，冰精灵，毒精灵。 这些精灵形成了$D$个部落，每一个部落都占有一个格子， 火精灵，冰精灵，毒精灵的部落分别用'A','B','C'表示。 在和一个部落成为朋友之前，部落也是不允许经过的。 要和一个部落成为朋友，必须给予对应属性的精华。 在地图上恰好有$D$个精华，火之精华，冰之精华，毒之精华分别用'a','b','c'表示。 每一个精华只能拿取一次，和一个部落成为朋友会消耗对应的精华， 一旦和一个部落成为朋友就可以永久通行。 小马们可以带领幸存的小马上下左右移动，每行动一格会耗费1个单位时间。 和部落交友、拿取精华不消耗时间。 无序存在的每一秒对小马国来说都是巨大的威胁，因此， 小马们必须以最快的速度从中心城$(1, 1)$逃到郊区$(n,m)$。

第一行三个整数$n,m,D$，表示网格的行、列和部落(精华)的个数。 接下来$n$行$m$列的字符矩形表示网格图。

一行一个整数，表示从中心城$(1, 1)$逃到郊区$(n,m)$的最短时间。

对于$30\%$的数据 $n,m \leq 5,D\leq 3$ 对于$60\%$的数据 $n,m \leq 100,D\leq 5$ 对于$80\%$的数据 $n,m\leq 1000, D\leq 8$ 对于$100\%$的数据 $n,m\leq 1000, D\leq 9$ 题解：http://blog.leanote.com/post/rockdu/b64d2eb333a1