Divisor de Grade N×M

Você recebe uma grade com N linhas e M colunas. Cada célula contém 0 (espaço vazio) ou 1 (bloqueada).

É garantido que todos os espaços vazios formam uma única região conexa.

Determine quantas formas é possível colocar apenas uma célula bloqueada de forma que os espaços vazios restantes se dividam em 2 ou mais grupos conectados distintos.

A primeira linha contém dois inteiros $N$ e $M$ $(1 \le N, M \le 5*10^3)$.

As próximas $N$ linhas contêm cada uma uma string hexadecimal de exatamente $\lceil M/4 \rceil$ caracteres (0–9, a–f), representando as células daquela linha de forma compactada.

Formato hexadecimal

Cada caractere hex representa 4 células consecutivas, com o bit mais significativo correspondendo à célula mais à esquerda (0 = vazia, 1 = bloqueada). Se $M$ não é múltiplo de 4, o último caractere usa apenas os bits mais significativos; os bits restantes são ignorados.

Tabela de conversão:

Exemplo com M=6 (2 hex chars, últimos 2 bits do segundo char ignorados):

Imprima um único inteiro: o número de células vazias cuja remoção divide a região em 2 ou mais grupos conectados.