有一个迷宫,迷宫由 n 行 m 列的字符组成,在迷宫中'.'代表该位置可以通过,'*'表示该位置是障碍,不能通过;当然,你只能在迷宫中行走,不能走出迷宫。
初始状态下,你在第 r 行,第 c 列的格子中,你可以沿着上下左右四个方向移动到非障碍格中。
在迷宫中移动,还有一个非常特殊的要求,向左最多只能移动不超过 x 格,向右最多只能移动不超过 y 格;上下两个方向没有任何限制。
请问:从出发点开始,最多可以走过多少个格子?(请注意:本题出发点也算在统计的格子总数中)
第1行有2个整数,n和m,分别表示迷宫的行和列数;(1≤n,m≤2000)
第2行有2个整数r和c,表示出发点的位于第r行第c列;(1≤r≤n,1≤c≤m)
第3行有2个整数x和y,表示向左和向右最多能够移动的次数(1≤x,y≤109)
接下来有n行,每行有m个字符,每个字符不是'.'就是'*';
本题确保出发点不是障碍。
输出一个整数,表示从起点出发,最多能够走到的格子数(含起点)。
4 5 3 2 1 2 ..... .***. ...** *....
10
4 4 2 2 0 1 .... ..*. .... ....
7
【样例解释1】
样例1中能够走到的点,用+
标记出来的结果如下图所示:
+++..
+***.
+++**
*+++.
【样例解释2】
样例2中能够走到的点,用+
标记出来的结果如下图所示:
.++.
.+*.
.++.
.++.