#QY0068. 城市大富翁

城市大富翁

题目背景

Dw 晚上一直睡不着,于是想出一道题,但不知道出什么题,于是翻了翻9934小游戏,找到了《大富翁》,于是就出现了你眼前这道题。

题目简介

Y小Y 很喜欢玩 “城市大富翁”,这个游戏的规则是这样的:

你一开始出生在坐标为 x,yx, y 的格子上(x为行,y为列),整个城市为一个 nmn * m 的方格图,"OO"表示可收购商店,"NN"表示不可被收购的地区。你需要收购尽量多的商店。

你出生的那个格子一开始就是一个可收购商店,且已经被你收购了。现在,你可以收购你上,下,左,右的可收购商店,并且你可收购商店的上,下,左,右的可收购商店又可以被你收购,以此类推。

如果你的商店到了城市边缘(上边缘,下边缘,左边缘,右边缘),那么你就可以传送到与城市边缘相对的边缘位置(例如(1, 3)中,x 为 1,是边缘,那么就可以传送到(n, 3)。又例如(4, m),y 为 m,是边缘,那么就可以传送到(4, 1)。),但前提是这个位置是一个可收购的商店,且并未被你收购过

但是,你也不可以一直传送下去,因此,你不能在已经传送过一次的前提下再次传送,因此你只能传送回原来的位置

现在,给出城市的长宽 n,mn, m,以及 Y小Y 的初始位置 x,yx, y,请你设计程序,求出 Y小Y 最终最多能收购多少个商店。

输入输出

输入

第一行四个正整数 n,m,x,yn, m, x, y,意义如题目简介所示。

接下来 nn 行,每行 mm 个字符,字符只能是 'O', 'N' 中的一个,表示地图中的方格。

输出

一个正整数,表示 Y小Y 最终收购的商店数量。

样例

5 4 4 3
NONN
OONO
NOON
NNON
NNON
8

样例解释

小Y 出生在 4, 3 的位置,他可以先收购 (1, 2), (2, 1), (2, 2), (3, 2), (3, 3), (4, 3), (5, 3),发现 (1, 2), (2, 1), (5, 3)都在边缘位置,则 小Y 可以传送到 (5, 2), (2, 4), (1, 3) 的位置,(5, 2) 与 (1, 3) 都是无法被收购的区域,只能传送回去,而 (2, 4) 的位置并未被收购,因此可以传送到这里,并收购 (2, 4) 处的商店。发现没有其他通路了,因此有 8 个商店被收购,输出 8。

数据规模与约定

对于 100% 的数据,保证 1n,m,x,y10001 \leq n, m, x, y \leq 1000