Descreva um algoritmo generalizado que receba uma matriz de dados (grid) e um parâmetro função 'valido(p)' que…

Questão

Descreva um algoritmo generalizado que receba uma matriz de dados (grid) e um parâmetro função 'valido(p)' que indica se um ponto pode ser explorado; o algoritmo deve coletar todas as regiões conectadas de pontos válidos. Inclua assinatura, pré-condições, pseudocódigo (iterativo ou recursivo) e explique como o parâmetro altera o comportamento sem mudar o corpo do algoritmo.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Assinatura: coletarRegioes(grid, valido) Pré-condições: grid é matriz m×n; valido(p) aceita coordenada ou valor; operações de vizinhança definidas (4 ou 8 vizinhos). Pseudocódigo (DFS iterativo): function coletarRegioes(grid, valido): m,n ? dimensões(grid) visitado ? matriz m×n false regioes ? lista vazia for i from 0 to m-1: for j from 0 to n-1: if not visitado[i][j] and valido(grid[i][j]): pilha ? [(i,j)] regiao ? lista vazia while pilha not empty: (r,c) ? pop(pilha) if visitado[r][c]: continue visitado[r][c] ? true if not valido(grid[r][c]): continue append regiao, (r,c) for cada vizinho (nr,nc) de (r,c) dentro dos limites: if not visitado[nr][nc]: push(pilha,(nr,nc)) append regioes, regiao return regioes Observações: - A função 'valido' determina se um ponto pertence a uma região (ex.: valor>limite, tipo específico). - O corpo do algoritmo não muda; basta passar diferentes implementações de 'valido' para alterar critérios (ex.: por cor, altitude, sensor). - Evite variáveis globais: 'visitado' e estruturas são locais à função para garantir reutilização e evitar efeitos colaterais. Expansão: pode usar BFS para ordem diferente ou adaptar vizinhança (4/8) sem modificar lógica principal, apenas a função de vizinhança ou 'valido'.

Explicação

A resposta apresenta um algoritmo claro e estruturado, utilizando uma abordagem de busca em profundidade (DFS) para explorar regiões conectadas em uma matriz. A flexibilidade do parâmetro 'valido' permite que diferentes critérios de validação sejam aplicados sem modificar a lógica central do algoritmo, demonstrando sua adaptabilidade. Além disso, a escolha de evitar variáveis globais e manter estruturas locais contribui para a reutilização e a segurança do código.

Raio-X da questão

Questões parecidas com resolução

• Projete um algoritmo recursivo em pseudocódigo que, dada uma matriz m×n com valores 0 e 1, retorne o tamanho da maior…
• Desenhe um algoritmo em pseudocódigo que, dada uma matriz M[N][M] com 0 (livre) e 1 (bloqueado), identifique todas as…
• Dada uma matriz m×n de inteiros (representando pontos de um mapa), escreva em pseudocódigo um algoritmo recursivo que…
• Projete um algoritmo em pseudocódigo que, dada uma matriz M com m linhas e n colunas de inteiros, determine quantos…
• Projete um algoritmo generalizado que receba uma coleção de registros e uma função parâmetro 'valida(reg)' que indique…
• Pesquisadores acompanham há três anos o avanço de resíduos flutuantes em um trecho de rio urbano. Em uma simulação para…

Todas as questões de Decomposição