Codeforces Round 293 (Div. 2) |
---|
Закончено |
На очередном заседании правящей партии «A» министр Павел предложил усовершенствовать систему водопровода и проложить в городе новую трубу.
Город на карте представляет собой прямоугольное клетчатое поле размера n × m. Каждая клетка поля либо свободна (тогда труба может проходить по ней), либо занята (по такой клетке труба проходить не может). На карте свободные клетки обозначены символом '.', а занятые — '#'.
Труба должна удовлетворят следующим свойствам:
Примеры разрешенных маршрутов для прокладывания труб:
....# ....# .*..#
***** ****. .***.
..#.. ..#*. ..#*.
#...# #..*# #..*#
..... ...*. ...*.
Примеры запрещенных маршрутов для прокладывания труб:
.**.# *...# .*.*#
..... ****. .*.*.
..#.. ..#*. .*#*.
#...# #..*# #*.*#
..... ...*. .***.
В примерах трубы обозначены символами ' * '.
Вам поручили написать программу, которая вычисляет количество различных способов проложить ровно одну трубу на территории города.
Два способа прокладывания труб считаются различными, если они отличаются хотя бы в одной клетке.
В первой строке входных данных следуют два целых числа n, m (2 ≤ n, m ≤ 2000) — размеры карты Берляндии.
В следующих n строках задано по m символов — карта города.
Если клетка карты обозначена символом '.', значит она свободна, и по ней может проходить труба.
Если клетка карты обозначена символом '#', значит она занята, и труба по ней проходить не может.
Выведите в первую строку выходных данных одно целое число — количество различных способов проложить ровно одну трубу.
3 3
...
..#
...
3
4 2
..
..
..
..
2
4 5
#...#
#...#
###.#
###.#
4
В первом примере существует 3 способа проложить трубу (клетки трубы обозначены символами ' * '):
.*. .*. ...
.*# **# **#
.*. ... .*.
Название |
---|