| Educational Codeforces Round 31 |
|---|
| Закончено |
Вам задана матрица размера n × m, состоящая из нулей и единиц. Необходимо определить количество компонент связности, состоящих из единиц. Две клетки входят в одну компоненту связности, если они смежны по стороне и в них стоят единицы.
Обратите внимание на ограничение памяти!
В первой строке следуют два целых числа n и m (1 ≤ n ≤ 212, 4 ≤ m ≤ 214) — количество строк и количество столбцов в матрице. Гарантируется, что m кратно четырём.
Далее следует описание матрицы. В каждой из n следующих строк следуют по 
однозначных числа шестнадцатеричной системы счисления (то есть, эти числа могут задаваться либо как цифры от 0 до 9, либо как прописные латинские буквы от A до F). Двоичная запись каждого из этих чисел задаёт очередные 4 элемента матрицы в текущей строке. Например, если число равно B, то очередные четыре элемента матрицы равны 1011, а если число равно 5, то очередные четыре элемента матрицы равны 0101.
Элементы в каждой строке задаются без пробелов.
Выведите количество компонент связности, состоящих из единиц.
3 4
1
A
8
3
2 8
5F
E3
2
1 4
0
0
В первом примере матрица имеет вид:
0001
1010
1000
Очевидно, что в ней три компоненты связности из единиц.
Во втором примере матрица имеет вид:
01011111
11100011
Очевидно, что в ней две компоненты связности из единиц.
В третьем примере в матрице нет ни одной единицы, поэтому ответ равен нулю.
