7152: 让你玩
[Creator : ]
Description
国庆七天乐,Y老师发现小智和小码这么喜欢玩游戏,就故意给他们出了一个游戏(难题)让他们玩。
这个游戏非常简单,Y老师画了一个 $n \times m$ 的矩形,再随手拿来了围棋。随手将白棋和黑棋撒在了矩形内,问小智和小码,黑棋通过以下规则最多可以拿出几颗。
1、黑棋可以上下左右四个方向移动,但是不能碰到白棋。(有白棋在的位置不能走)
2、只要将黑棋移动到了矩形边界,就认为该黑棋可以拿出来。
为了方便我们用 ‘.’ 表示当前位置没有棋。
1:表示白棋,不允许通过,当前敌人也不会移动。
0:表示黑棋,可以随意移动。
这个游戏非常简单,Y老师画了一个 $n \times m$ 的矩形,再随手拿来了围棋。随手将白棋和黑棋撒在了矩形内,问小智和小码,黑棋通过以下规则最多可以拿出几颗。
1、黑棋可以上下左右四个方向移动,但是不能碰到白棋。(有白棋在的位置不能走)
2、只要将黑棋移动到了矩形边界,就认为该黑棋可以拿出来。
为了方便我们用 ‘.’ 表示当前位置没有棋。
1:表示白棋,不允许通过,当前敌人也不会移动。
0:表示黑棋,可以随意移动。
Input
第一行输入两个数 $n,m$;
接下来输入一个 $n \times m$ 的矩形。
接下来输入一个 $n \times m$ 的矩形。
Output
输出最多可以拿出的黑棋数量。
Constraints
$1 \leq n,m \leq 1,000$
Sample 1 Input
4 5
111..
101..
111..
..0..
Sample 1 Output
1