Em processamento de imagens, usualmente, as imagens digitais são representadas utilizando matrizes bidimensionais e algumas operações básicas são definidas a partir de transformações matriciais. Em geral, estas transformações levam em conta os valores de células desta matriz localizadas em uma determinada vizinhança. Por exemplo, a transformação chamada erosão, em uma vizinhança 3 \times 3, calcula, para cada célula da matriz, o mínimo entre o valor da própria célula e o de seus vizinhos distantes em até uma célula (incluindo diagonais).
Escreva um programa que lê os tamanhos das duas dimensões de uma matriz M, e a própria matriz (ou seja, os valores de suas células) e, subsequentemente, calcula e mostra na tela o resultado da erosão de M. Note que a vizinhança é válida somente dentro da matriz.
Por exemplo, para a matriz 5 \times 5
\left[\begin{array}{lllll} 1 & 1 & 1 & 1 & 0 \\\\ 1 & 1 & 1 & 1 & 1 \\\\ 1 & 1 & 0 & 1 & 1 \\\\ 1 & 1 & 1 & 1 & 1 \\\\ 1 & 1 & 1 & 1 & 1 \end{array}\right]
deve-se imprimir
\left[\begin{array}{lllll} 1 & 1 & 1 & 0 & 0 \\\\ 1 & 0 & 0 & 0 & 0 \\\\ 1 & 0 & 0 & 0 & 1 \\\\ 1 & 0 & 0 & 0 & 1 \\\\ 1 & 1 & 1 & 1 & 1 \end{array}\right]
Assuma que o número de linhas e colunas desta matriz é sempre menor ou igual a 30 .

Passo 1

O enunciado pede que se leia uma matriz bidimensional e que se calcule a sua “erosão” usando uma vizinhança 3\times3. Mais precisamente:
  • Entradas fornecidas: o número de linhas e colunas da matriz (cada uma \le 30) e os valores de todas as células da matriz M.
  • Operação pedida: para cada posição da matriz, calcular o mínimo entre o valor da própria célula e os valores de seus vizinhos que estejam a uma distância de até uma célula (ou seja, deslocamentos -1,0,1 tanto em linhas quanto em colunas), incluindo diagonais. A vizinhança só considera posições válidas dentro dos limites da matriz.
  • Saída esperada: imprimir a matriz resultante da erosão (mesmo formato de linhas e colunas, uma linha por linha).
Informações relevantes do enunciado:
  • A vizinhança 3\times3 inclui até 9 células, mas nas bordas e cantos há menos células válidas (apenas as que existem dentro da matriz).
  • Exemplo dado no enunciado (peguei estes dados do enunciado): matriz 5\times5
\left[\begin{array}{lllll} 1 & 1 & 1 & 1 & 0 \\\\ 1 & 1 & 1 & 1 & 1 \\\\ 1 & 1 & 0 & 1 & 1 \\\\ 1 & 1 & 1 & 1 & 1 \\\\ 1 & 1 & 1 & 1 & 1 \end{array}\right]
deve produzir
\left[\begin{array}{lllll} 1 & 1 & 1 & 0 & 0 \\\\ 1 & 0 & 0 & 0 & 0 \\\\ 1 & 0 & 0 & 0 & 1 \\\\ 1 & 0 & 0 & 0 & 1 \\\\ 1 & 1 & 1 & 1 & 1 \end{array}\right].

Passo 2

Definição matemática clara da operação que vamos implementar. Seja M a matriz de entrada com R linhas e C colunas, indexadas de 0 a R-1 e 0 a C-1. Definimos a matriz erodida E por
E_{i,j}=\min\bigl\{M_{r,c}\mid r\in\{i-1,i,i+1\},\; c\in\{j-1,j,j+1\},\; 0\le r<R,\;0\le c<C\bigr\}.
Isto significa: para cada célula (i,j) pegamos todos os pares (r,c) que estão dentro do quadrado 3\times3 centrado em (i,j) e que também estão dentro dos limites da matriz; entre esses valores tomamos o mínimo.

Passo 3

Como lidar com bordas (caso importante): na expressão acima as coordenadas (r,c) são restritas por 0\le r<R e 0\le c<C. Na prática, ao calcular E_{i,j} iteramos sobre \Delta r\in\{-1,0,1\} e \Delta c\in\{-1,0,1\}, definimos r=i+\Delta r e c=j+\Delta c e só usamos M_{r,c} se r e c estiverem dentro dos limites. Assim, cantos usam 4 células, bordas laterais usam 6 células, e posições internas usam 9 células.

Passo 4

Complexidade e justificativa do método: para cada célula fazemos no máximo 9 comparações, logo o custo total é O(R\cdot C) com constante 9 — totalmente adequado para R,C\le 30. O algoritmo é simples, direto e não precisa de estruturas avançadas.

Passo 5

Vou mostrar cálculos manuais em algumas células do exemplo (peguei os valores do enunciado) para que fique claro o procedimento.
  • Canto superior esquerdo (0,0): vizinhança válida tem (0,0),(0,1),(1,0),(1,1) com valores \{1,1,1,1\}. Então
E_{0,0}=\min\{1,1,1,1\}=1.
  • Célula (0,3): vizinhança válida abrange linhas 0 e 1 e colunas 2,3,4. Os valores desses índices (peguei da matriz do enunciado) são \{1,1,0,1,1,1\} — note que há um 0 em (0,4). Logo
E_{0,3}=\min\{1,1,0,1,1,1\}=0.
  • Célula central (2,2): sua vizinhança é completa 3\times3 e inclui o próprio valor M_{2,2}=0. Assim
E_{2,2}=\min(\text{vizinhança})=0.ç
  • Canto inferior direito (4,4): vizinhança válida são (3,3),(3,4),(4,3),(4,4) e todos esses são 1 (peguei da matriz do enunciado), então
E_{4,4}=1.
Esses resultados parciais coincidem com a matriz final esperada mostrada no enunciado.

Passo 6

Estratégia de implementação prática (passo a passo):
  1. Ler R e C.
  2. Ler R linhas com C inteiros cada, armazenando em uma lista de listas M.
  3. Criar uma matriz E de tamanho R\times C inicializada (por exemplo com zeros).
  4. Para cada índice i de 0 até R-1 e cada j de 0 até C-1:
    • Inicializar um valor grande m (por exemplo infinito).
    • Para cada \Delta r\in\{-1,0,1\} e \Delta c\in\{-1,0,1\}:
      • Calcular r=i+\Delta r e c=j+\Delta c.
      • Se 0\le r<R e 0\le c<C então atualizar m=\min(m,M_{r,c}).
    • Atribuir E_{i,j}=m.
  5. Imprimir E com cada linha em uma linha de saída, elementos separados por espaço.
Formato de entrada/saída esperado (forma usual):
  • Entrada: primeira linha com dois inteiros R e C, seguidos por R linhas contendo C inteiros cada (separados por espaços).
  • Saída: R linhas, cada uma com C inteiros (separados por espaço), representando a matriz erodida.

Passo 7

Dicas rápidas para a prova:
  • Não complique: a operação é local e fixa (3x3). Faça dois laços para percorrer a matriz e dois laços aninhados com \Delta r,\Delta c\in\{-1,0,1\}.
  • Lembre de checar os limites (condição 0\le r<R e 0\le c<C); esquecer isso é a fonte mais comum de erro.
  • Para depurar, calcule manualmente alguns elementos na margem (cantos/bordas) — são os que mais confundem.

Resposta

#!/usr/bin/env python3
import sys

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    R = int(next(it))
    C = int(next(it))
    M = [[0]*C for _ in range(R)]
    for i in range(R):
        for j in range\text{(C)}:
            try:
                M[i][j] = int(next(it))
            except StopIteration:
                M[i][j] = 0

    E = [[0]*C for _ in range(R)]
    for i in range(R):
        for j in range\text{(C)}:
            mval = 10**18  # valor grande inicial
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    r = i + dr
                    c = j + dc
                    if 0 <= r < R and 0 <= c < C:
                        v = M[r][c]
                        if v < mval:
                            mval = v
            E[i][j] = mval

    out_lines = []
    for row in E:
        out_lines.append(" ".join(str(x) for x in row))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Exercícios relacionados