Introdução aos Algoritmos de Busca
Em programação competitiva, frequentemente enfrentamos problemas que envolvem encontrar caminhos, contar componentes conectados, ou explorar espaços de estados. Dois algoritmos fundamentais dominam essas situações: Busca em Largura (BFS) e Busca em Profundidade (DFS). Este artigo apresenta implementações práticas e técnicas de otimização para esses algoritmos.
Flood Fill - Encontrando Componentes Conectados
O algoritmo flood fill é usado para encontrar componentes conectados em uma matriz. A ideia principal é explorar todos os vizinhos de uma célula usando BFS, marcando células visitadas para evitar processamento repetido.
Problema: Contagem de Lagos
Dado um grid onde 'W' representa água e '.' representa terra, contar o número de lagos (componentes conectados de água). Usamos movimento em 8 direções.
#include <bits/stdc++.h>
using namespace std;
struct Ponto {
int x, y;
};
const int MAXN = 1010;
int n, m;
char grade[MAXN][MAXN];
bool visitado[MAXN][MAXN];
Ponto fila[MAXN * MAXN];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
void explorarComponente(int sx, int sy) {
int inicio = 0, fim = 0;
fila[0] = {sx, sy};
visitado[sx][sy] = true;
while (inicio <= fim) {
Ponto atual = fila[inicio++];
for (int dir = 0; dir < 8; dir++) {
int nx = atual.x + dx[dir];
int ny = atual.y + dy[dir];
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
!visitado[nx][ny] && grade[nx][ny] == 'W') {
visitado[nx][ny] = true;
fila[++fim] = {nx, ny};
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> grade[i];
}
int contador = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grade[i][j] == 'W' && !visitado[i][j]) {
explorarComponente(i, j);
contador++;
}
}
}
cout << contador << endl;
return 0;
}
Problema do Castelo
Este problema demonstra como usar representação binária para representar barreiras. Cada célula contém um número onde cada bit indica se existe uma parede em uma direção específica.
#include <bits/stdc++.h>
using namespace std;
struct Ponto {
int x, y;
};
const int MAXN = 55;
int n, m;
int grade[MAXN][MAXN];
bool visitado[MAXN][MAXN];
Ponto fila[MAXN * MAXN];
int maiorArea = 0;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void explorarCastelo(int sx, int sy) {
int inicio = 0, fim = 0;
int area = 1;
fila[0] = {sx, sy};
visitado[sx][sy] = true;
while (inicio <= fim) {
Ponto atual = fila[inicio++];
for (int dir = 0; dir < 4; dir++) {
int nx = atual.x + dx[dir];
int ny = atual.y + dy[dir];
// Verificar se há parede nesta direção usando bits
if (!(grade[atual.x][atual.y] & (1 << dir)) &&
nx >= 0 && nx < n && ny >= 0 && ny < m &&
!visitado[nx][ny]) {
visitado[nx][ny] = true;
fila[++fim] = {nx, ny};
area++;
}
}
}
maiorArea = max(maiorArea, area);
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grade[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visitado[i][j]) {
explorarCastelo(i, j);
}
}
}
cout << maiorArea << endl;
return 0;
}
Vales e Picos
Para determinar vales e picos, verificmaos se um componente tem vizinhença apenas com valores maiores (pico) ou apenas com valores menores (vale).
#include <bits/stdc++.h>
using namespace std;
struct Ponto {
int x, y;
};
const int MAXN = 1010;
int n;
int altitude[MAXN][MAXN];
bool visitado[MAXN][MAXN];
Ponto fila[MAXN * MAXN];
void explorarRegiao(int sx, int sy, bool& temMaior, bool& temMenor) {
int inicio = 0, fim = 0;
fila[0] = {sx, sy};
visitado[sx][sy] = true;
while (inicio <= fim) {
Ponto atual = fila[inicio++];
for (int i = atual.x - 1; i <= atual.x + 1; i++) {
for (int j = atual.y - 1; j <= atual.y + 1; j++) {
if (i < 0 || i >= n || j < 0 || j >= n) continue;
if (i == atual.x && j == atual.y) continue;
int vizinho = altitude[i][j];
int atualVal = altitude[atual.x][atual.y];
if (vizinho != atualVal) {
if (vizinho > atualVal) temMaior = true;
else temMenor = true;
} else if (!visitado[i][j]) {
visitado[i][j] = true;
fila[++fim] = {i, j};
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> altitude[i][j];
}
}
int picos = 0, vales = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visitado[i][j]) {
bool temMaior = false, temMenor = false;
explorarRegiao(i, j, temMaior, temMenor);
if (!temMaior) picos++;
if (!temMenor) vales++;
}
}
}
cout << picos << " " << vales << endl;
return 0;
}
BFS com Rastreamento de Caminho
Para recuperar o caminho percorrido em uma busca BFS, mantemos uma matriz de predecessores que registra de qual célula viemos para cada célula visitada.
#include <cstring>
#include <iostream>
using namespace std;
struct Ponto {
int x, y;
};
const int MAXN = 1010;
int n;
int grade[MAXN][MAXN];
Ponto fila[MAXN * MAXN];
Ponto predecessor[MAXN][MAXN];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void buscaLargura(int sx, int sy) {
int inicio = 0, fim = 0;
fila[0] = {sx, sy};
// Inicializar predecessor como inválido
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
predecessor[i][j] = {-1, -1};
}
}
while (inicio <= fim) {
Ponto atual = fila[inicio++];
for (int dir = 0; dir < 4; dir++) {
int nx = atual.x + dx[dir];
int ny = atual.y + dy[dir];
if (nx >= 0 && nx < n && ny >= 0 && ny < n &&
grade[nx][ny] == 0 && predecessor[nx][ny].x == -1) {
fila[++fim] = {nx, ny};
predecessor[nx][ny] = atual;
}
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> grade[i][j];
}
}
buscaLargura(n - 1, n - 1);
Ponto atual = {0, 0};
while (true) {
cout << atual.x << " " << atual.y << endl;
if (atual.x == n - 1 && atual.y == n - 1) break;
atual = predecessor[atual.x][atual.y];
}
return 0;
}
Cavaleiro de Samurai
Este problema requer movimento em "L", similar ao cavaleiro no xadrez. Precisamos definir os 8 deslocamentos possíveis.
#include <bits/stdc++.h>
using namespace std;
struct Ponto {
int x, y;
};
const int MAXN = 405;
int n, m;
char grade[MAXN][MAXN];
int distancia[MAXN][MAXN];
Ponto fila[MAXN * MAXN];
int dx[8] = {-2, -2, 2, 2, -1, 1, -1, 1};
int dy[8] = {1, -1, 1, -1, -2, -2, 2, 2};
int buscarDistancia(Ponto inicio, Ponto fim) {
memset(distancia, -1, sizeof(distancia));
int inicioIdx = 0, fimIdx = 0;
fila[0] = inicio;
distancia[inicio.x][inicio.y] = 0;
while (inicioIdx <= fimIdx) {
Ponto atual = fila[inicioIdx++];
for (int dir = 0; dir < 8; dir++) {
int nx = atual.x + dx[dir];
int ny = atual.y + dy[dir];
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
grade[nx][ny] != '*' && distancia[nx][ny] == -1) {
fila[++fimIdx] = {nx, ny};
distancia[nx][ny] = distancia[atual.x][atual.y] + 1;
if (nx == fim.x && ny == fim.y) {
return distancia[nx][ny];
}
}
}
}
return -1;
}
int main() {
cin >> n >> m;
Ponto inicio, fim;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grade[i][j];
if (grade[i][j] == 'K') inicio = {i, j};
if (grade[i][j] == 'H') fim = {i, j};
}
}
cout << buscarDistancia(inicio, fim) << endl;
return 0;
}
Distância em Linha Reta
Para grafos onde todas as arestas têm peso 1, BFS encontra a menor distância. Este exemplo mostra o problema clássico de encontrar a menor distância antre dois pontos em uma reta numérica com operações de incremento, decremento e dobro.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int n, k;
int distancia[MAXN];
int fila[MAXN];
int buscarDistanciaMinima() {
memset(distancia, -1, sizeof(distancia));
int inicio = 0, fim = 0;
fila[0] = n;
distancia[n] = 0;
while (inicio <= fim) {
int atual = fila[inicio++];
if (atual == k) return distancia[atual];
// Tentar n+1
if (atual + 1 < MAXN && distancia[atual + 1] == -1) {
fila[++fim] = atual + 1;
distancia[atual + 1] = distancia[atual] + 1;
}
// Tentar n-1
if (atual - 1 >= 0 && distancia[atual - 1] == -1) {
fila[++fim] = atual - 1;
distancia[atual - 1] = distancia[atual] + 1;
}
// Tentar n*2
if (atual * 2 < MAXN && distancia[atual * 2] == -1) {
fila[++fim] = atual * 2;
distancia[atual * 2] = distancia[atual] + 1;
}
}
return -1;
}
int main() {
cin >> n >> k;
cout << buscarDistanciaMinima() << endl;
return 0;
}
Matriz de Distâncias
Este problema inverte a perspectiva: em vez de encontrar a distância de um ponto a todos os outros, encontramos a distância de todos os pontos ao conjunto de pontos iniciais (células com valor 1).
#include <bits/stdc++.h>
using namespace std;
struct Ponto {
int x, y;
};
const int MAXN = 1010;
int n, m;
int grade[MAXN][MAXN];
int distancia[MAXN][MAXN];
Ponto fila[MAXN * MAXN];
void calcularDistancias() {
int inicio = 0, fim = 0;
// Inicializar todos os pontos com 1 como fonte
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
distancia[i][j] = -1;
if (grade[i][j] == 1) {
fila[fim++] = {i, j};
distancia[i][j] = 0;
}
}
}
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
while (inicio < fim) {
Ponto atual = fila[inicio++];
for (int dir = 0; dir < 4; dir++) {
int nx = atual.x + dx[dir];
int ny = atual.y + dy[dir];
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
distancia[nx][ny] == -1) {
distancia[nx][ny] = distancia[atual.x][atual.y] + 1;
fila[fim++] = {nx, ny};
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grade[i][j];
}
}
calcularDistancias();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << distancia[i][j] << " ";
}
cout << endl;
}
return 0;
}
Problema do Tapete Mágico
Este problema envolve transformar um estado inicial em um estado final usando operações de transformação de string. Usamos BFS para encontrar a sequência mínima de operações.
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, pair<string, char>> antecessor;
string operacaoA(string estado) {
for (int i = 0; i < 4; i++) swap(estado[i], estado[7 - i]);
return estado;
}
string operacaoB(string estado) {
for (int i = 0; i < 3; i++) {
swap(estado[2 - i], estado[3 - i]);
swap(estado[4 + i], estado[5 + i]);
}
return estado;
}
string operacaoC(string estado) {
swap(estado[1], estado[2]);
swap(estado[5], estado[6]);
swap(estado[1], estado[5]);
return estado;
}
void buscarMenorCaminho(string inicio, string fim) {
queue<string> fila;
fila.push(inicio);
while (!fila.empty()) {
string atual = fila.front();
fila.pop();
if (atual == fim) return;
string proximos[3];
proximos[0] = operacaoA(atual);
proximos[1] = operacaoB(atual);
proximos[2] = operacaoC(atual);
for (int i = 0; i < 3; i++) {
if (!antecessor.count(proximos[i])) {
fila.push(proximos[i]);
antecessor[proximos[i]] = {atual, char('A' + i)};
}
}
}
}
int main() {
int x;
string inicio = "12345678", fim;
for (int i = 0; i < 8; i++) {
cin >> x;
fim += char(x + '0');
}
buscarMenorCaminho(inicio, fim);
string resultado;
while (fim != inicio) {
resultado = antecessor[fim].second + resultado;
fim = antecessor[fim].first;
}
if (resultado.empty()) cout << 0 << endl;
else cout << resultado.length() << resultado << endl;
return 0;
}
Circuito Elétrico - Deque BFS
Para custos de aresta iguais a 0 ou 1, usamos uma deque (double-ended queue) em vez de uma fila comum. Isso permite inserir elementos no início (custo 0) ou no final (custo 1).
#include <bits/stdc++.h>
using namespace std;
struct Ponto {
int x, y;
};
const int MAXN = 510;
int n, m;
char grade[MAXN][MAXN];
int distancia[MAXN][MAXN];
bool visitado[MAXN][MAXN];
int buscarMenorCusto() {
memset(distancia, 0x3f, sizeof(distancia));
memset(visitado, 0, sizeof(visitado));
deque<Ponto> fila;
distancia[0][0] = 0;
fila.push_back({0, 0});
// Mapeamento de caracteres para direções
char esperado[] = {'\\', '/', '/', '\\'};
int dx[4] = {-1, -1, 1, 1};
int dy[4] = {-1, 1, 1, -1};
int ix[4] = {-1, -1, 0, 0};
int iy[4] = {-1, 0, 0, -1};
while (!fila.empty()) {
Ponto atual = fila.front();
fila.pop_front();
if (visitado[atual.x][atual.y]) continue;
visitado[atual.x][atual.y] = true;
for (int dir = 0; dir < 4; dir++) {
int nx = atual.x + dx[dir];
int ny = atual.y + dy[dir];
if (nx < 0 || nx > n || ny < 0 || ny > m) continue;
int celulaX = atual.x + ix[dir];
int celulaY = atual.y + iy[dir];
int custo = distancia[atual.x][atual.y] +
(grade[celulaX][celulaY] != esperado[dir]);
if (custo < distancia[nx][ny]) {
distancia[nx][ny] = custo;
if (grade[celulaX][celulaY] != esperado[dir]) {
fila.push_back({nx, ny});
} else {
fila.push_front({nx, ny});
}
}
}
}
return distancia[n][m];
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> grade[i];
}
int resultado = buscarMenorCusto();
if (resultado == 0x3f3f3f3f) {
cout << "NO SOLUTION" << endl;
} else {
cout << resultado << endl;
}
}
return 0;
}
Busca Bidirecional
Quando sabemos o estado inicial e o estado final, podemos buscar de ambos os lados simultaneamente. Isso reduz a complexidade de O(b^d) para O(b^(d/2)).
#include <bits/stdc++.h>
using namespace std;
int n;
string inicio, fim;
string a[6], b[6];
unordered_map<string, int> distInicio, distFim;
int expandir(queue<string>& fila, unordered_map<string, int>& da,
unordered_map<string, int>& db, string de[], string para[]) {
int nivel = da[fila.front()];
while (!fila.empty() && da[fila.front()] == nivel) {
string atual = fila.front();
fila.pop();
for (int i = 0; i < n; i++) {
for (int pos = 0; pos < (int)atual.size(); pos++) {
if (atual.substr(pos, a[i].size()) == a[i]) {
string nova = atual.substr(0, pos) + b[i] +
atual.substr(pos + a[i].size());
if (db.count(nova)) {
return da[atual] + db[nova] + 1;
}
if (da.count(nova)) continue;
da[nova] = da[atual] + 1;
fila.push(nova);
}
}
}
}
return 11;
}
int buscaBidirecional() {
if (inicio == fim) return 0;
queue<string> qInicio, qFim;
qInicio.push(inicio);
qFim.push(fim);
distInicio[inicio] = distFim[fim] = 0;
int passos = 0;
while (!qInicio.empty() && !qFim.empty()) {
int resultado;
if (qInicio.size() < qFim.size()) {
resultado = expandir(qInicio, distInicio, distFim, a, b);
} else {
resultado = expandir(qFim, distFim, distInicio, b, a);
}
if (resultado <= 10) return resultado;
if (++passos == 10) return -1;
}
return -1;
}
int main() {
cin >> inicio >> fim;
while (cin >> a[n] >> b[n]) n++;
int resultado = buscaBidirecional();
if (resultado == -1) cout << "NO ANSWER!" << endl;
else cout << resultado << endl;
return 0;
}
Problema de Agrupamento de Dados
Gatos na Montanha
Este problema usa DFS com backtracking para distribuir itens em grupos, tentando minimizar o número de grupos necessários.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20;
int n, m;
int pesos[MAXN];
int capacidade[MAXN];
int melhorResposta = MAXN;
void buscar(int indice, int numGrupos) {
if (numGrupos >= melhorResposta) return;
if (indice == n) {
melhorResposta = numGrupos;
return;
}
// Tentar colocar no grupo existente
for (int i = 0; i < numGrupos; i++) {
if (capacidade[i] + pesos[indice] <= m) {
capacidade[i] += pesos[indice];
buscar(indice + 1, numGrupos);
capacidade[i] -= pesos[indice];
}
}
// Criar novo grupo
capacidade[numGrupos] = pesos[indice];
buscar(indice + 1, numGrupos + 1);
capacidade[numGrupos] = 0;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> pesos[i];
// Ordenar decrescente para melhor performance
sort(pesos, pesos + n, greater<int>());
buscar(0, 0);
cout << melhorResposta << endl;
return 0;
}
Busca em Labirinto com Atualizações
Para problemas com múltiplas consultas e atualizações de obstáculos, podemos usar uma abordagem de "rebuild periódico". Quando o número de pontos modificados excede um limite, recalculamos todas as distâncias.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Celula {
ll x, y, z, distancia;
};
ll idx(ll x, ll y, ll z, ll n, ll m, ll h) {
return (x - 1) + (y - 1) * n + (z - 1) * n * m;
}
ll n, m, h, q;
vector<ll> distancia;
queue<Celula> filaModificada;
ll dx[6] = {1, 0, 0, -1, 0, 0};
ll dy[6] = {0, 1, 0, 0, -1, 0};
ll dz[6] = {0, 0, 1, 0, 0, -1};
bool valido(ll x, ll y, ll z) {
return x >= 1 && x <= n && y >= 1 && y <= m && z >= 1 && z <= h;
}
void recalcularDistancias() {
while (!filaModificada.empty()) {
Celula atual = filaModificada.front();
filaModificada.pop();
for (int dir = 0; dir < 6; dir++) {
ll nx = atual.x + dx[dir];
ll ny = atual.y + dy[dir];
ll nz = atual.z + dz[dir];
if (!valido(nx, ny, nz)) continue;
ll idProx = idx(nx, ny, nz, n, m, h);
if (distancia[idProx] > atual.distancia + 1) {
filaModificada.push({nx, ny, nz, atual.distancia + 1});
distancia[idProx] = atual.distancia + 1;
}
}
}
}
int main() {
ll t;
cin >> t;
while (t--) {
cin >> n >> m >> h >> q;
distancia.assign(n * m * h + 1, 1e18);
filaModificada = queue<Celula>();
for (ll i = 0; i < q; i++) {
ll op, x, y, z;
cin >> op >> x >> y >> z;
if (op == 1) {
ll id = idx(x, y, z, n, m, h);
distancia[id] = 1;
filaModificada.push({x, y, z, 1});
} else {
recalcularDistancias();
ll id = idx(x, y, z, n, m, h);
cout << distancia[id] - 1 << endl;
}
}
}
return 0;
}
Cavaleiro com Obstáculos
Este problema adiciona a complexidade de "cavalos bloqueados" - o cavalo não pode pular sobre obstáculos.
#include <bits/stdc++.h>
using namespace std;
struct No {
int x, y, passos;
};
const int MAXN = 310;
int n, m, k;
int obstaculo[MAXN][MAXN];
bool visitado[MAXN][MAXN];
int dx[8] = {-2, -2, 2, 2, -1, 1, -1, 1};
int dy[8] = {1, -1, 1, -1, -2, -2, 2, 2};
int buscar(int sx, int sy, int ex, int ey, bool verificarPulo) {
memset(visitado, 0, sizeof(visitado));
queue<No> fila;
fila.push({sx, sy, 0});
visitado[sx][sy] = true;
while (!fila.empty()) {
No atual = fila.front();
fila.pop();
if (atual.x == ex && atual.y == ey) {
return atual.passos;
}
for (int dir = 0; dir < 8; dir++) {
int nx = atual.x + dx[dir];
int ny = atual.y + dy[dir];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (obstaculo[nx][ny]) continue;
if (visitado[nx][ny]) continue;
if (verificarPulo) {
if (abs(dx[dir]) == 2) {
int meioX = atual.x + dx[dir] / 2;
if (obstaculo[meioX][atual.y]) continue;
} else {
int meioY = atual.y + dy[dir] / 2;
if (obstaculo[atual.x][meioY]) continue;
}
}
visitado[nx][ny] = true;
fila.push({nx, ny, atual.passos + 1});
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
cin >> n >> m;
cin >> k;
memset(obstaculo, 0, sizeof(obstaculo));
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
obstaculo[x][y] = 1;
}
// Sem verificação de salto e com verificação
cout << buscar(1, 1, n, m, false) << " ";
cout << buscar(1, 1, n, m, true) << endl;
}
return 0;
}
Conclusão
Os algoritmos BFS e DFS são fundamentais em programação competitiva. A escolha entre eles depende do problema:
- BFS: Quando precisamos encontrar o menor caminho em grafos não ponderados, ou quando queremos explorar níveis uniformes primeiro.
- DFS: Quando precisamos explorar todas as possibilidades, especialmente com backtracking e poda.
- Deque BFS: Quando temos custos de aresta 0 ou 1.
- Busca Bidirecional: Quando conhecemos tanto o estado inicial quanto o final.
As técnicas de poda, como limitar a profundidade de busca ou ordenar elementos antes da busca, podem reduzir significativamente o tempo de execução em espaços de estados grandes.