← 返回题目列表

Codeforces · 884/E

E. 二进制矩阵

中文机器翻译题面 查看原题

给定一个大小为 n × m 的矩阵。矩阵的每个元素要么是 1,要么是 0。您必须确定由 1 组成的连通分量的数量。如果两个单元格具有共同边框,并且这些单元格中的两个元素均为 1,则它们属于同一组件。

注意内存限制不寻常!

输入

第一行包含两个数字 n 和 m (1 ≤ n ≤ 212, 4 ≤ m ≤ 214) — 分别是行数和列数。保证m能被4整除。

那么矩阵的表示如下。接下来的 n 行中的每一行都包含 $$\frac{m}{4}$$ 一位十六进制数字(也就是说,这些数字可以表示为 0 到 9 的数字,也可以表示为 A 到 F 的大写拉丁字母)。每个数字的二进制表示表示相应行中矩阵的接下来 4 个元素。例如,如果给出数字B,那么对应的元素是1011,如果数字是5,那么对应的元素是0101。

元素不以空格分隔。

输出

打印由 1 组成的连接分量的数量。

示例

输入 #1

3 4
1
A
8

输出 #1

3

输入 #2

2 8
5F
E3

输出 #2

2

输入 #3

1 4
0

输出 #3

0

注意

在第一个示例中,矩阵为:

很明显,它由三个组成部分组成。

第二个例子:

显然,组件数量为 2。

第三个示例中没有 1,因此答案为 0。