Síntese: qual padrão usar?
Cinco padrões de matriz cobertos. Hora de treinar o reflexo: ler um problema de grid e saber qual ferramenta sacar — com justificativa.
A árvore de decisão da seção
1. Preciso PERCORRER/PRODUZIR a matriz numa ordem especial (espiral, camadas)?
→ TRAVESSIA POR CAMADAS (quatro limites que encolhem)
2. Preciso TRANSFORMAR a matriz sem memória extra (girar, zerar)?
→ IN-PLACE: decompor (transpor + inverter) e/ou usar a 1ª linha/coluna
como marcadores
3. A pergunta é sobre REGIÕES CONECTADAS (ilhas, áreas, preencher)?
→ DFS / FLOOD FILL (marca permanente; cobre a região)
4. Preciso achar/contar CAMINHOS específicos (palavra, todos os caminhos)?
→ BACKTRACKING (DFS com marca temporária: marca → explora → desmarca)
5. A pergunta é "o caminho MAIS CURTO / menos passos"?
→ BFS (fila, camadas de distância crescente)
E os reflexos da seção inteira: nomeie as duas dimensões no Big-O (O(m·n), não O(n²)), sempre cheque os limites antes de acessar um vizinho, e lembre que grid é grafo — DFS/BFS são as ferramentas centrais.
O mapa completo da seção
| Padrão | Pergunta-chave | Estrutura | Tempo | Espaço |
|---|---|---|---|---|
| Travessia espiral | "percorrer em espiral/camadas" | 4 limites | O(m·n) | O(1) |
| Transformação in-place | "girar/zerar sem cópia" | índices + marcadores | O(m·n) | O(1) |
| DFS / flood fill | "regiões conectadas" | pilha (recursão) | O(m·n) | O(m·n) |
| Backtracking | "caminho específico / todos" | DFS + desfazer | O(m·n·4ᴸ) | O(L) |
| BFS | "caminho mais curto" | fila | O(m·n) | O(m·n) |
A ideia que une metade da seção: o grid é um grafo, e DFS (fundo), backtracking (fundo + desfazer) e BFS (largura) são três modos de percorrê-lo, cada um para um tipo de pergunta. Você sai daqui pronto para a seção de Grafos, onde esses mesmos algoritmos aparecem sem a "muleta" da grade regular.
Quiz da seção
Enunciados que você não viu nas aulas. Identifique o padrão e o porquê. 7+ acertos: pronto para a prova.
🧠 Quiz da seção: Matriz
0/81. 'Calcule a área da maior ilha de 1s num grid.' Qual padrão?
2. 'Quantos passos para uma laranja podre apodrecer todas as vizinhas, em minutos?' (multi-fonte). Qual padrão?
3. 'Gere uma matriz n×n preenchida em espiral com 1..n².' Qual padrão?
4. 'Encontre se existe um caminho que soletra uma palavra por células adjacentes (sem reusar).' Qual padrão?
5. 'Distância de cada célula até o 0 mais próximo (01 Matrix).' Qual padrão?
6. Por que a complexidade de visitar uma matriz 1000×3 é O(m·n) = 3000, e não O(n²) = 1.000.000?
7. Qual a ideia-mãe que conecta DFS, backtracking e BFS nesta seção?
8. 'Capture as regiões de O cercadas por X (as que não tocam a borda).' Qual a sacada?
Pronto para a prova?
A prova final da seção Matriz tem três problemas inéditos — fácil, médio e difícil — com casos ocultos. O difícil (capturar regiões cercadas) pede a sacada de inverter o problema e fazer DFS a partir das bordas: exatamente o tipo de raciocínio que a árvore de decisão acima treina.
Boa prova! Volte para a página da seção e clique em "Prova final".