← 返回题目列表

Codeforces · 1063/B

B. 迷宫

中文机器翻译题面 查看原题

您正在玩一些电脑游戏。其中一个关卡让您置身于由 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 ≤ 109)——分别允许向左和向右移动的最大次数。

接下来的 n 行描述了迷宫。它们的长度均为 m,仅由符号“.”组成。和 '*'。第 i 行的第 j 个字符对应于迷宫第 i 行 j 列的单元格。象征 '。'表示空闲单元,而符号“*”表示有障碍物的单元。

保证起始单元格不包含任何障碍物。

输出

精确打印一个整数 - 迷宫中从起始单元格可到达的单元格数量,包括起始单元格本身。

示例

输入 #1

4 5
3 2
1 2
.....
.***.
...**
*....

输出 #1

10

输入 #2

4 4
2 2
0 1
....
..*.
....
....

输出 #2

7

注意

在相应示例中可到达的单元格标有“+”。

第一个例子:

+++..+***.+++***+++.

第二个例子:

.++..+*..++..++.