Domenico 可以操控天气。在某次作战中,他需要将
�
×
�
n×m 的矩形范围内某些位置变成晴天、某些位置变成雨天。
最开始这
�
×
�
n×m 的空间范围内都是晴天。Domenico 可以进行任意次如下操作:
选择一块四联通区域,将区域变成晴天或雨天。
Domenico 想要知道最少需要进行多少次操作才可以完成任务。
输入格式
第一行两个整数
�
,
�
n,m,表示空间范围。
接下来
�
n 行,每行
�
m 个字符。
0
0 表示任务要求该位置为晴天,
1
1 表示任务要求该位置为雨天。
输出格式
输出一行一个正整数,表示最少需要的操作次数。
input1
复制代码
4 4
1011
1100
1111
0011
output1
复制代码
2
数据范围
对于
100
%
100% 的数据,保证
1
⩽
�
,
�
⩽
50
1⩽n,m⩽50。
子任务点编号 分值
�
⩽
n⩽
�
⩽
m⩽
1
1
19
19
15
15
15
15
2
2
7
7
1
1
50
50
3
3
25
25
30
30
30
30
4
4
49
49
50
50
50
50
下发样例
附件