Descrição do Problema

Uma matriz retangular é preenchida com dígitos de 0 a 9, onde os valores de 1 a 9 representam células. Uma célula é definida como uma região contínua de dígitos não-zero, conectada vertical ou horizontalmente. O objetivo é determinar o número total de células na matriz fornecida.

Formato de Entrada

A primeira linha contém dois inteiros, n e m, indicando as dimensões da matriz.

As subsequentes n linhas consistem em strings de comprimento m com caracteres entre '0' e '9', representando a matriz.

Formato de Saída

Uma única linha com um inteiro que corresponde à contagem de células.

Exemplo

Entrada:

4 10
0234500067
1034560500
2045600671
0000000089

Saída:

4

Restrições

Para 100% dos casos de teste, 1 ≤ n, m ≤ 100.

Abordagem de Solução

Este problema é semelhante a encontrar componentes conectados em uma grade. Utilizamos busca em profundidade (DFS) para identificar e contar regiões contínuas de dígitos não-zero. Abaixo, apresentamos duas implementações em Python.

A primeira abordagem emprega uma estrutura de dados de visitados para controlar posições já processadas.

def contar_celulas():
    linhas, colunas = map(int, input().strip().split())
    matriz = []
    for _ in range(linhas):
        elementos = [c for c in input().strip()]
        matriz.append(elementos)
    explorado = [[False for _ in range(colunas)] for _ in range(linhas)]
    
    def dfs(coordenada_x, coordenada_y):
        if matriz[coordenada_x][coordenada_y] == '0':
            return
        if explorado[coordenada_x][coordenada_y]:
            return
        explorado[coordenada_x][coordenada_y] = True
        deslocamentos = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        for dx, dy in deslocamentos:
            novo_x, novo_y = coordenada_x + dx, coordenada_y + dy
            if 0 <= novo_x < linhas and 0 <= novo_y < colunas:
                dfs(novo_x, novo_y)
    
    total_celulas = 0
    for i in range(linhas):
        for j in range(colunas):
            if matriz[i][j] != '0' and not explorado[i][j]:
                dfs(i, j)
                total_celulas += 1
    return total_celulas

print(contar_celulas())

A segunda abordagem altera diretamente a matriz durante a DFS, definindo células visitadas como '0' para evitar revisitação.

def explorar_celula(matriz, pos_x, pos_y):
    if matriz[pos_x][pos_y] != '0':
        matriz[pos_x][pos_y] = '0'
        direcoes = [(-1, 0), (0, -1), (1, 0), (0, 1)]
        for delta_x, delta_y in direcoes:
            x_adj, y_adj = pos_x + delta_x, pos_y + delta_y
            if 0 <= x_adj < len(matriz) and 0 <= y_adj < len(matriz[0]):
                explorar_celula(matriz, x_adj, y_adj)

def principal():
    n_linhas, n_colunas = map(int, input().strip().split())
    grade = []
    for _ in range(n_linhas):
        grade.append(list(input().strip()))
    quantidade = 0
    for idx_linha in range(n_linhas):
        for idx_coluna in range(n_colunas):
            if grade[idx_linha][idx_coluna] != '0':
                explorar_celula(grade, idx_linha, idx_coluna)
                quantidade += 1
    return quantidade

print(principal())

A segunda implementação pode reduzir o uso de memória ao eliminar a necessidade de uma matriz de visitados separdaa.