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.
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
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
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):
Ler R e C.
Ler R linhas com C inteiros cada, armazenando em uma lista de listas M.
Criar uma matriz E de tamanho R\times C inicializada (por exemplo com zeros).
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.
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 python3import sys
defmain():
data = sys.stdin.read().strip().split()
ifnot data:
return
it = iter(data)
R = int(next(it))
C = int(next(it))
M = [[0]*C for _ inrange(R)]
for i inrange(R):
for j inrange\text{(C)}:
try:
M[i][j] = int(next(it))
except StopIteration:
M[i][j] = 0
E = [[0]*C for _ inrange(R)]
for i inrange(R):
for j inrange\text{(C)}:
mval = 10**18# valor grande inicialfor dr in (-1, 0, 1):
for dc in (-1, 0, 1):
r = i + dr
c = j + dc
if0 <= r < R and0 <= 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()