20220221 - 迷宫

时间限制

1000 毫秒

内存限制

128 MB

通过次数

9

提交次数

27

有一个nm列的迷宫,.表示空地*表示障碍。现在你位于迷宫的rc列。当你上下左右移动时只能移动到空地,不能移动到障碍或地图外,每移动一格需要按下键盘上对应的上下左右键一次。非常不幸的是,你的键盘坏了,所以你只能向左移动不超过x格,向右移动不超过y格,而上下键并没有坏掉。

在满足如上条件的情况下,从起点出发,有多少格子是可以到达的(包含起点)?

输入

第一行,n,m,r,c,x,y

接下来n行,每行一个长度为m.*构成的字符串。

对于100%的数据:

1 \le n,m \le 2×10^3

1 \le r \le n

1 \le c \le m

1\le x,y \le 10^9

输出

一个整数,表示含起点在内有多少个格子是可以到达的。

样例

输入

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

输出

10

输入

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

输出

7