Стековый Лабиринт
Вам предстоит пройти через лабиринт, представленный в виде сетки размером W×H. Верхний левый угол сетки — это ячейка (1, 1), а нижний правый — ячейка (W, H). Вы начинаете свой путь в ячейке (1, 1) и должны добраться до ячейки (W, H). Разрешено перемещаться только в соседнюю ячейку справа или вниз. Пример лабиринта показан на рисунке ниже.
В лабиринте некоторые ячейки свободны (обозначены '.'), а некоторые заняты камнями (обозначены '#'), в которые нельзя войти. В некоторых свободных ячейках находятся драгоценности (обозначены строчными буквами), а в других — отверстия для размещения драгоценностей (обозначены заглавными буквами). Каждая строчная буква соответствует определённому типу драгоценности, а заглавная — отверстию для неё. Например, ячейка с '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 ≤ W, H ≤ 50. Остальная часть набора данных состоит из H строк, каждая из которых содержит W символов. Символ C_ij указывает тип ячейки (i, j), как описано выше. Гарантируется, что C_11 и C_WH никогда не равны '#'.
Также гарантируется, что каждая строчная или заглавная буква появляется не более 10 раз в каждом наборе данных.
Выходные данные
Для каждого набора данных выведите максимальное количество драгоценностей, которые можно разместить в соответствующие отверстия. Если невозможно добраться до ячейки (W, H), выведите -1.