Desenhe um algoritmo em pseudocódigo que, dada uma matriz M[N][M] com 0 (livre) e 1 (bloqueado), identifique…

Questão

Desenhe um algoritmo em pseudocódigo que, dada uma matriz M[N][M] com 0 (livre) e 1 (bloqueado), identifique todas as regiões conectadas de células livres usando 4-vizinhança e retorne a lista dos tamanhos de cada região. Descreva as estruturas de dados, o pseudocódigo e a complexidade.

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

Resposta esperada

Estruturas de dados: matriz M[N][M] de entrada, matriz booleana visited[N][M] inicializada em False, fila (queue) ou pilha (stack) para BFS/DFS, lista sizes para armazenar tamanhos. Pseudocódigo (BFS/Flood fill): sizes := [] visited := matriz N×M com False for i from 0 to N-1 do for j from 0 to M-1 do if M[i][j] == 0 and not visited[i][j] then count := 0 queue.enqueue((i,j)) visited[i][j] := True while queue not empty do (r,c) := queue.dequeue() count := count + 1 for (dr,dc) in [(1,0),(-1,0),(0,1),(0,-1)] do nr := r + dr; nc := c + dc if nr in [0..N-1] and nc in [0..M-1] and M[nr][nc] == 0 and not visited[nr][nc] then visited[nr][nc] := True queue.enqueue((nr,nc)) sizes.append(count) return sizes Análise de complexidade: Cada célula é visitada no máximo uma vez; cada aresta de vizinhança é considerada constante vezes. Tempo: O(N*M). Espaço extra: O(N*M) para visited e até O(N*M) na fila no pior caso. Observações: usar DFS (pilha/recursão) produz resultado equivalente; para grandes matrizes iterativas com fila são preferíveis para evitar estouro de pilha. Para 8-vizinhança, ajustar offsets de vizinhança.

Explicação

O algoritmo utiliza uma abordagem de busca em largura (BFS) para explorar todas as células livres conectadas, garantindo que cada célula seja visitada uma única vez, o que resulta em uma complexidade de tempo linear em relação ao número total de células. A estrutura de dados escolhida, como a matriz booleana para controle de visitação e a fila para gerenciar a exploração, é adequada para evitar revisitações e garantir a correta contagem das regiões. Além disso, a análise de complexidade considera tanto o tempo quanto o espaço, refletindo a eficiência do algoritmo em diferentes cenários.

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

Todas as questões de Algoritmos