问题陈述
有一个迷宫,可以描述为 W \times H 网格。 左上单元格表示为 (1, 1),右下单元格表示为 (W, H)。 您现在位于牢房 (1, 1),必须前往该牢房 (W, H)。 但是,您只能移至右侧相邻单元格或下方相邻单元格。 下图是一个迷宫的示例。
...#...... a###.##### .bc...A... ##.#C#d#.# .#B#.#.### .#...#e.D. .#A..###.# ..e.c#..E. ####d###.# #....#.#.# ##E...d.C.
在迷宫中,一些细胞是自由的(表示为 .)并且一些单元格被岩石占据(表示为 #),您无法进入。
在一些空闲单元中还有宝石(用小写字母表示)和放置宝石的孔(用大写字母表示)。
不同的字母对应不同类型的珠宝,即由 a 包含 A 型宝石,以及由 A 包含一个用于放置 A 型宝石的孔。
据说,当我们将宝石放入相应的孔中时,就会发生幸福的事情。
在有宝石的单元格中,您可以选择是否挑选宝石。 同样,在有孔的单元格中,您可以选择是否放置您拥有的珠宝。 最初您没有任何珠宝。 你有一个很大的包,所以你可以带任意多的珠宝。 不过,你的包是一堆的,也就是说,你只能放置最后拿起的珠宝。
从单元格 (1, 1) 到单元格的途中 (W, H),您可以放置多少颗宝石来纠正孔?
输入
输入包含一系列数据集。 输入的结尾由包含两个零的行表示。 每个数据集的格式如下。
H W
C_{11} C_{12} ... C_{1W}
C_{21} C_{22} ... C_{2W}
...
C_{H1} C_{H2} ... C_{HW}
在这里, H 和 W 是网格的高度和宽度。
你可能会假设 1 \leq W, H \leq 50。
其余数据集包括 H 行,每行由 W 字母。
每个字母 C_{ij} 指定单元格的类型 (i, j) 如前所述。
可以保证 C_{11} 和 C_{WH} 从来没有 #.
您还可以假设每个小写或大写字母在每个数据集中最多出现 10 次。
输出
对于每个数据集,输出可以放置到相应孔中的最大珠宝数量。 如果您无法到达牢房 (W, H),输出-1。
Sample Input 由
3 3 ac# b#C .BA 3 3 aaZ a#Z aZZ 3 3 ..# .#. #.. 1 50 abcdefghijklmnopqrstuvwxyYXWVUTSRQPONMLKJIHGFEDCBA 1 50 aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyY 1 50 abcdefghijklmnopqrstuvwxyABCDEFGHIJKLMNOPQRSTUVWXY 1 50 aaaaaaaaaabbbbbbbbbbcccccCCCCCBBBBBBBBBBAAAAAAAAAA 10 10 ...#...... a###.##### .bc...A... ##.#C#d#.# .#B#.#.### .#...#e.D. .#A..###.# ..e.c#..E. ####d###.# ##E...D.C. 0 0
样本输入的输出
2 0 -1 25 25 1 25 4