Задача №113935. Лабиринт
В одном из уровней компьютерной игры вы попали в лабиринт, состоящий из n строк, каждая из которых содержит m клеток. Каждая клетка либо свободна, либо занята препятствием. Стартовая клетка находится в строке r и столбце c . За один шаг вы можете переместиться на одну клетку вверх, влево, вниз или вправо, если она не занята препятствием. Вы не можете перемещаться за границы лабиринта.
К сожалению, ваша клавиатура крайне близка к поломке, поэтому вы можете переместиться влево не более x раз и вправо не более y раз. При этом ограничений на перемещения вверх и вниз нет, поскольку клавиши, используемые для движения вверх и вниз, всё ещё в идеальном состоянии.
Теперь вы для каждой клетки поля решили установить, можно ли выбрать такую последовательность нажатий, которая приведёт вас из стартовой в эту клетку. Посчитайте, сколько клеток поля обладают таким свойством.
Первая строка содержит два целых числа n , m ( 1 ≤ n , m ≤ 2000 ) — количество строк и столбцов в лабиринте, соответственно.
Вторая строка содержит два целых числа r , c ( 1 ≤ r ≤ n , 1 ≤ c ≤ m ) — номер строки и столбца, на пересечении которых расположена стартовая клетка.
Третья строка содержит два целых числа x , y ( 0 ≤ x , y ≤ 10 9 ) — максимальное количество перемещений влево и вправо, соответственно.
Следующие n строк содержат описание лабиринта. Каждая из этих строк имеет длину m и состоит только из символов ' . ' и ' * '. В i -й строке j -й символ соответствует клетке лабиринта с номерами строки и столбца i и j , соответственно. Символ ' . ' соответствует свободной клетке лабиринта, а символ ' * ' — клетке с препятствием.
Гарантируется, что стартовая клетка не занята препятствием.
Выведите одно число — количество клеток лабиринта, достижимых из стартовой, включая её саму.
Клетки, достижимые в соответствующем примере, отмечены ' + '.
Первый пример
+++..
+***.
+++**
*+++.
Второй пример
.++.
.+*.
.++.
.++.
4 5 3 2 1 2 ..... .***. ...** *....
10
4 4 2 2 0 1 .... ..*. .... ....
7