April Fools Day Contest 2021 |
---|
Закончено |
Мышь нашла большой красивый торт и решила прогуляться по нему, попутно объедая ягоды на верхушке торта. Торт прямоугольный и разделен на аккуратные квадраты; в некоторых квадратах есть ягода, а в некоторых нет.
Мышь спешит, поэтому когда она взберется на торт в его северо-западном углу (вернняя левая клетка входных данных), она будет двигаться только на восток (направо) или на юг (вниз), пока не достигнет юго-восточного угла (нижняя правая клетка). Она съест все ягоды на клетках, через которые она пройдет, и оставит остальные ягоды нетронутыми.
Мышь хочет выбрать свой путь так, чтобы съесть наибольшее возможное количество ягод. Но, возможно, ее спешка и голод затмевают ее разум и вынуждают ее принимать неоптимальные решения...
Первая строка входных данных состоит из двух чисел $$$H$$$ и $$$W$$$ ($$$1 \le H, W \le 5$$$), разделенных пробелом - высоты и ширины торта.
Следующие $$$H$$$ строк содержат строки из ровно $$$W$$$ символов, описывающих квадраты торта: «.» представляет пустой квадрат, а «*» - квадрат с ягодой.
Выведите одно число - количество ягод, которые съест мышь, следуя своей стратегии.
4 3 *.. .*. ..* ...
3
4 4 .*.. *... ...* ..*.
2
3 4 ..** *... ....
1
5 5 ..*.. ..... **... **... **...
1
Название |
---|