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

• Desenhe um algoritmo em pseudocódigo que, dada uma matriz M[N][M] com 0 (livre) e 1 (bloqueado), identifique todas as…
• Projete um algoritmo em pseudocódigo que, dada uma matriz M com m linhas e n colunas de inteiros, determine quantos…
• Descreva um algoritmo generalizado que receba uma matriz de dados (grid) e um parâmetro função 'valido(p)' que indica se…
• 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[m][n] de inteiros e um inteiro t (1 = t = min(m,n))…
• Projete um algoritmo em pseudocódigo que, dada uma matriz M de inteiros com m linhas e n colunas, construa e retorne uma…

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