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

• Os aplicativos de mapa, como o GPS, ajudam o carro de entregas a chegar à casa do cliente. O aplicativo compara dois…
• Lia organiza carrinhos, bonecas e blocos separando cada tipo, colocando-os em caixas e guardando as caixas na…
• Em um jogo, uma personagem controlada por IA precisa chegar a um tesouro sem bater nas paredes. Qual instrução ajuda a…
• Em um programa, Substring(codigo, início, quantidade) pega letras do texto a partir da posição indicada, e…
• Projete um algoritmo em pseudocódigo que, dadas as variáveis temperatura (inteiro ºC), ocupacao (inteiro, número de…
• Considere um algoritmo com duas estruturas de repetição aninhadas, cada uma iterando de 1 até n. Qual é a complexidade…

Todas as questões de Algoritmos