Разбор задач с acm.timus.ru. Задача 1033

В свободное время я иногда решаю задачки с тимуса. Для себя делаю пометки с краткой идеей решения. За 5 лет из накопилось весьма большое количество. Буду периодически публиковать их тут.

Начну с задачи 1033.

Решение достаточно прозрачно - необходимо обойти все проходимые клетки лабиринта и подсчитать количество стен в каждой.

Что значит проходимые? Это те, в которые можно попасть либо из верхнего левого угла, либо из нижнего правого. Кстати, условие не гарантирует пути из одного угла в другой.

Ниже приведены несколько тестов, взятых с форума.

Вход:

33
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
................................#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
...............................##
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#..#.#.#.#.#.#.#.#.#.#.#.#.#.#...
................................#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
...............................##
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#..#.#.#.#.#.#.#.#.#.#.#.#.#.#...
................................#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##.#.#.#.#.#.#.#.#.#.#.#.#.#.##..
................................#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
................................#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
...............................##
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#..#.#.#.#.#.#.#.#.#.#.#.#.#.#...
...............................##
#.##.#.#.#.#.#.#.#.#.#.#.#.#.#...
................................#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
...............................##
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#....

Ответ:

12402

Вход:

3
...
...
...

Ответ:

72

Вход:

3
.##
###
##.

Ответ:

36