Projete um algoritmo recursivo em pseudocódigo que, dada uma matriz m×n com valores 0 e 1, retorne o tamanho…

Questão

Projete um algoritmo recursivo em pseudocódigo que, dada uma matriz m×n com valores 0 e 1, retorne o tamanho da maior região conectada de 1s considerando conectividade em quatro direções. Justifique a escolha da estrutura de dados e como o algoritmo evita visitar a mesma célula várias vezes.

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

Resposta esperada

Resposta modelo (pseudocódigo): funcao maiorIlha(mat): maximo = 0 para i de 0 ate m-1: para j de 0 ate n-1: se mat[i][j] == 1 entao: tamanho = dfs(i,j) se tamanho > maximo entao maximo = tamanho retorne maximo funcao dfs(i,j): se i<0 ou i>=m ou j<0 ou j>=n ou mat[i][j]==0 entao retorne 0 mat[i][j] = 0 // marca visitado in-place cont = 1 cont += dfs(i+1,j) cont += dfs(i-1,j) cont += dfs(i,j+1) cont += dfs(i,j-1) retorne cont Justificativa da estrutura: usa-se a própria matriz como estrutura primária (acesso O(1) por índice) e marcação in-place para evitar um vetor adicional de 'visitados', reduzindo uso extra de memória. A recursão (DFS) é natural para explorar regiões conectadas; complexidade O(m·n) no pior caso e espaço de pilha O(m·n) no pior caso de região grande.

Explicação

O algoritmo utiliza uma abordagem recursiva para explorar cada célula da matriz, contando o tamanho das regiões conectadas de 1s. A marcação in-place evita a necessidade de uma estrutura adicional para rastrear células visitadas, economizando memória. A complexidade O(m·n) garante eficiência ao percorrer toda a matriz, enquanto a recursão permite uma exploração completa das conexões.

Raio-X da questão

Questões parecidas com resolução

• Após chuvas intensas, um ponto comunitário passou a organizar entregas de kits de higiene para famílias cadastradas. Os…
• “Uma fala apagada por engano não pode desaparecer do acervo”, observou a responsável pela digitalização de depoimentos…
• — Se fecharmos a válvula errada, o posto de saúde fica sem água — alertou a técnica durante a revisão do sistema…
• — Meu número é 12, mas há pessoas com atendimento prioritário antes de mim — observou uma moradora durante um mutirão de…
• — A fila está dobrando a esquina — avisou um voluntário da cozinha comunitária, enquanto outra pessoa anotava, em um…
• Uma professora quer calcular o total de pontos de cada aluno e percebe que a planilha atualiza os resultados quando o…

Todas as questões de Programação - Projetos com programação