画作

paint.cpp/in/out

• 时间限制：1s
• 内存限制：128MB

题目描述

小 G 喜欢作画，尤其喜欢仅使用黑白两色作画。

画作可以抽象成一个 $r \times c$ 大小的 01 矩阵。现在小 G 构思好了他的画作，准备动笔开始作画。初始时画布是全白的，他每一次下笔可以将一个四联通的部分涂成黑色或白色。

你需要告诉他，在给出的构思下，他最少需要下笔多少次才能完成画作。

输入格式

第一行两个正整数 $r, c$。

接下来 $r$ 行，每行 $c$ 个字符，表示目标画作。

输出格式

输出一行一个正整数，表示最少需要的下笔步数。

样例输入

3 3
010
101
010

样例输出

2

数据范围

• Subtask 1 (19pts)：$r \times c \le 15$。
• Subtask 2 (7pts)：$r = 1$。
• Subtask 3 (25pts)：$r, c \le 30$。
• Subtask 4 (49pts)：$r, c \le 50$。