Олимпиадный тренинг

Задача . E. Бинарная матрица

Задача

Вам задана матрица размера n × m, состоящая из нулей и единиц. Необходимо определить количество компонент связности, состоящих из единиц. Две клетки входят в одну компоненту связности, если они смежны по стороне и в них стоят единицы.

Обратите внимание на ограничение памяти!

Входные данные

В первой строке следуют два целых числа n и m (1 ≤ n ≤ 2¹², 4 ≤ m ≤ 2¹⁴) — количество строк и количество столбцов в матрице. Гарантируется, что m кратно четырём.

Далее следует описание матрицы. В каждой из n следующих строк следуют по $\text{[math]}$ однозначных числа шестнадцатеричной системы счисления (то есть, эти числа могут задаваться либо как цифры от 0 до 9, либо как прописные латинские буквы от A до F). Двоичная запись каждого из этих чисел задаёт очередные 4 элемента матрицы в текущей строке. Например, если число равно B, то очередные четыре элемента матрицы равны 1011, а если число равно 5, то очередные четыре элемента матрицы равны 0101.