A resolução de problemas que envolvem grades ou matrizes bidimensionais frequentemente se reduz a uma questão de teoria dos grafos. Cada célula pode ser vista como um nó, com arestas conectando vizinhos adjacentes. As técnicas fundamentais para navegar por essas estruturas são a Busca em Profundidade (DFS) e a Busca em Largura (BFS). Abaixo, exploramos quatro cenários clássicos onde o domínio desas travessias é essencial.
- Cálculo de Área de Terreno Isolado
O objetivo deste cenário é quantificar o número total de células de terra que não têm conexão direta ou indireta com as bordas externas do mapa. A estratégia padrão envolve duas fases distintas.
Fase de Limpeza: Inicialmente, partimos de todas as células nas bordas (primeira linha, última linha, primeira coluna, última coluna). Se encontrarmos terra nessas posições, iniciamos uma busca (DFS ou BFS) para marcar todo o território conectado a essa borda como "visível" ou "marítimo". Isso efetivamente isola as regiões verdadeiramente internas.
Fase de Contagem: Após a limpeza, iteramos sobre o interior da matriz. Qualquer célula de terra restante representa uma área isolada. Somamos essas células para obter o resultado final.
#include <iostream>
#include <vector>
using namespace std;
// Direções para movimento (cima, direita, baixo, esquerda)
const int direcoes[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// Função recursiva para explorar componente conectado
void explorar_componente(vector<vector<int>> &mapa_terreno, int r, int c) {
// Marca a célula atual como água (0) após visitação
mapa_terreno[r][c] = 0;
int linhas = mapa_terreno.size();
int colunas = mapa_terreno[0].size();
for (auto &d : direcoes) {
int pr = r + d[0];
int pc = c + d[1];
// Validação de limites e verificação se é terra
if (pr >= 0 && pr < linhas && pc >= 0 && pc < colunas && mapa_terreno[pr][pc] == 1) {
explorar_componente(mapa_terreno, pr, pc);
}
}
}
int contar_area_isolada() {
int N, M;
cin >> N >> M;
vector<vector<int>> mapa(N, vector<int>(M));
// Leitura da entrada
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> mapa[i][j];
}
}
// Eliminar terra conectada às bordas laterais
for (int i = 0; i < N; ++i) {
if (mapa[i][0] == 1) explorar_componente(mapa, i, 0);
if (mapa[i][M - 1] == 1) explorar_componente(mapa, i, M - 1);
}
// Eliminar terra conectada às bordas superior e inferior
for (int j = 0; j < M; ++j) {
if (mapa[0][j] == 1) explorar_componente(mapa, 0, j);
if (mapa[N - 1][j] == 1) explorar_componente(mapa, N - 1, j);
}
// Contar o restante
int area_total = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (mapa[i][j] == 1) {
area_total++;
}
}
}
return area_total;
}
- Afundamento de Ilhas Internas
Neste problema, devemos modificar o estado do mapa. Toda ilha que toca a borda deve permanecer intacta (ou ser restaurada), enquanto ilhas completamente cercadas pela água devem afundar (virar água). Utilizamos uma técnica de marcação temporária para distinguir os dois estados durante o processamento.
Fluxo da Solução:
- Percurso pelas bordas: Identifique todo terreno acessível a partir das fronteiras e marque-o com um valor especial (ex: 2).
- Atualização Global: Varra toda a grade. Onde houver o valor original de terra (1) mas sem a marcação especial, transforme em água (0).
- Restauração: Transforme todas as marcas temporárias (2) de volta para terra (1).
void marcar_acesso_bordas(vector<vector<int>> &grid, int r, int c, int R, int C) {
if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] != 1) return;
grid[r][c] = 2; // Marca como acessível
marcar_acesso_bordas(grid, r - 1, c, R, C);
marcar_acesso_bordas(grid, r + 1, c, R, C);
marcar_acesso_bordas(grid, r, c - 1, R, C);
marcar_acesso_bordas(grid, r, c + 1, R, C);
}
// Implementação simplificada do fluxo principal
int resolver_afundamento() {
int n, m;
cin >> n >> m;
vector<vector<int>> grade(n, vector<int>(m));
for(auto &row : grade) for(int &x : row) cin >> x;
// Passo 1: Marcar terras conectadas à borda
for(int i = 0; i < n; i++) {
if(grade[i][0] == 1) marcar_acesso_bordas(grade, i, 0, n, m);
if(grade[i][m-1] == 1) marcar_acesso_bordas(grade, i, m-1, n, m);
}
for(int j = 0; j < m; j++) {
if(grade[0][j] == 1) marcar_acesso_bordas(grade, 0, j, n, m);
if(grade[n-1][j] == 1) marcar_acesso_bordas(grade, n-1, j, n, m);
}
// Passo 2: Normalizar o estado da grade
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grade[i][j] == 1) grade[i][j] = 0; // Ilha interna afunda
else if(grade[i][j] == 2) grade[i][j] = 1; // Borda resta
}
}
// Saída da grade modificada
for(const auto &row : grade) {
for(int val : row) cout << val << " ";
cout << endl;
}
return 0;
}
- Pontos de Escoamento Dual (Água)
Determinar quais células permitem que a água flua tanto para o Oceano Pacífico quanto para o Oceano Atlântico exige considerar a altitude do terreno. A água flui de altitudes maiores ou iguais para menores.
Otimização Essencial: A abordagem ingênua verifica cada ponto individualmente, resultando em complexidade excessiva ($O(N \cdot M \cdot \text{DFS})$). A solução eficiente inverte a lógica: começamos dos oceanos (bordas) e sobemos montanha acima.
- Matriz PacificoAcessivel: Armazena pontos alcançáveis desde a borda Norte/Oeste.
- Matriz AtlanticoAcessivel: Armazena pontos alcançáveis desde a borda Sul/Leste.
Qualqeur célula presente em ambas as matrizes é um ponto válido.
#include <iostream>
#include <vector>
using namespace std;
const int vet_direcao[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
void preencher_alcancais(const vector<vector<int>> &alturas, vector<vector<bool>> &pode_chegar, int r, int c, int H, int W) {
if(r < 0 || r >= H || c < 0 || c >= W || pode_chegar[r][c]) return;
pode_chegar[r][c] = true;
for(int k = 0; k < 4; k++) {
int nr = r + vet_direcao[k][0];
int nc = c + vet_direcao[k][1];
if(nr >= 0 && nr < H && nc >= 0 && nc < W) {
// Só podemos subir se a altura do vizinho for >= atual
if(alturas[nr][nc] >= alturas[r][c]) {
preencher_alcancais(alturas, pode_chegar, nr, nc, H, W);
}
}
}
}
void encontrar_conluencia() {
int N, M;
cin >> N >> M;
vector<vector<int>> mapa_altura(N, vector<int>(M));
for(int i=0; i<n cin="" for="" i="" j="0;">> mapa_altura[i][j];
vector<vector<bool>> pacifico(N, vector<bool>(M, false));
vector<vector<bool>> atlantico(N, vector<bool>(M, false));
// Inicia buscas a partir das bordas correspondentes
for(int i = 0; i < N; i++) {
preencher_alcancais(mapa_altura, pacifico, i, 0, N, M); // Oeste
preencher_alcancais(mapa_altura, atlantico, i, M - 1, N, M); // Leste
}
for(int j = 0; j < M; j++) {
preencher_alcancais(mapa_altura, pacifico, 0, j, N, M); // Norte
preencher_alcancais(mapa_altura, atlantico, N - 1, j, N, M); // Sul
}
// Coleta resultados
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(pacifico[i][j] && atlantico[i][j]) {
cout << i << " " << j << endl;
}
}
}
}</n>
- Maximização de Ilha Única
Este desafio consiste em converter exatamente uma célula de água em terra para conectar componentes existentes, maximizando a área total resultante.
Abordagem de Agrupamento:
- Identifique todos os grupos de ilhas existentes usando DFS, atribuindo um ID único a cada grupo e registrando sua área individual em um mapa/hash table.
- Itere sobre todas as células de água. Para cada célula de água candidata, analise seus vizinhos. Some as áreas dos grupos distintos de ilhas adjacentes.
- O resultado é a soma máxima encontrada mais 1 (a nova célula adicionada).
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int direcoes_movimento[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
// Calcula tamanho do componente e marca com ID
int calcular_tamanho_e_marcar(vector<vector<int>> &terreno,
vector<vector<bool>> &visitado,
int x, int y, int id_ilha, int R, int C) {
visitado[x][y] = true;
terreno[x][y] = id_ilha;
int area = 1;
for(auto &d : direcoes_movimento) {
int nx = x + d[0], ny = y + d[1];
if(nx >= 0 && nx < R && ny >= 0 && ny < C && !visitado[nx][ny] && terreno[nx][ny] == 1) {
area += calcular_tamanho_e_marcar(terreno, visitado, nx, ny, id_ilha, R, C);
}
}
return area;
}
int main() {
int R, C;
cin >> R >> C;
vector<vector<int>> matricula(R, vector<int>(C));
for(auto &line : matricula) for(int &val : line) cin >> val;
unordered_map<int, int> areas_por_id;
vector<vector<bool>> ja_visitado(R, vector<bool>(C, false));
int id_atual = 2;
bool apenas_terra = true;
// Passo 1: Agrupar ilhas
for(int i=0; i<r :="" apenas_terra="false;" area="calcular_tamanho_e_marcar(matricula," areas_por_id="" c="" conex="" cout="" d="" de="" direcoes_movimento="" endl="" for="" i="" id_atual="" ids_vizinhos="" if="" int="" j="0;" ja_visitado="" maior_extensao="0;" matricula="" ni="i" nj="j" passo="" r="" return="" tentativa="" unordered_set="" via="">= 0 && ni < R && nj >= 0 && nj < C && matricula[ni][nj] > 1) {
ids_vizinhos.insert(matricula[ni][nj]);
}
}
int area_potencial = 1; // +1 pela própria célula de água virando terra
for(int id : ids_vizinhos) {
area_potencial += areas_por_id[id];
}
if(area_potencial > maior_extensao) {
maior_extensao = area_potencial;
}
}
}
}
cout << max(maior_extensao, 1) << endl; // Caso existam apenas águas
return 0;
}</r>