← 返回题目列表

AtCoder · icpc2012autumn_e

E. 堆栈迷宫

中文机器翻译题面 查看原题

问题陈述

有一个迷宫,可以描述为 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