A implementação abaixo demonstra uma busca binária recursiva em um array ordenado. O critério de parada é quando o limite esquerdo ultrapassa o direito.
#include <iostream>
using namespace std;
int encontrarElemento(int *vetor, int alvo, int esquerda, int direita) {
if (esquerda > direita) return 0; // Elemento não encontrado
int meio = (direita + esquerda) / 2;
if (vetor[meio] > alvo) return encontrarElemento(vetor, alvo, esquerda, meio - 1);
else if (vetor[meio] < alvo) return encontrarElemento(vetor, alvo, meio + 1, direita);
else return 1; // Elemento encontrado
}
int main() {
int n, m, vetor[1000], alvos[50000];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> vetor[i];
}
cin >> m;
for (int i = 0; i < m; i++) {
cin >> alvos[i];
}
for(int i = 0; i < m; i++) {
if (encontrarElemento(vetor, alvos[i], 0, n - 1))
printf("Sim\n");
else
printf("Não\n");
}
return 0;
}
- Algoritmo QuickSort
O QuickSort utiliza a estratégia de divisão e conqusita, selecionando um elemento pivô e particionando o array em torno dele.
#include <iostream>
using namespace std;
void ordenacaoRapida(int *vetor, int esquerda, int direita) {
if(esquerda >= direita) return; // Condição de saída
int pivo = vetor[esquerda], i = esquerda, j = direita;
while(i != j) {
while(i != j && pivo < vetor[j]) j--;
vetor[i] = vetor[j];
while(i != j && pivo >= vetor[i]) i++;
vetor[j] = vetor[i];
}
vetor[i] = pivo; // Posicionamento final do pivô
ordenacaoRapida(vetor, esquerda, i - 1); // Parte esquerda
ordenacaoRapida(vetor, i + 1, direita); // Parte direita
}
int main() {
int n, vetor[10000];
cin >> n;
for(int i = 0; i < n; i++) {
cin >> vetor[i];
}
ordenacaoRapida(vetor, 0, n - 1);
for(int i = 0; i < n; i++) {
cout << vetor[i] << endl;
}
return 0;
}
- Busca em Profundidade (DFS): Resolução de Labirintos
Este algoritmo utiliza DFS para encontrar um caminho em um labirinto representado por uma matriz.
#include <iostream>
using namespace std;
#define TAM_MAX 20
typedef struct coordenada {
int linha;
int coluna;
} Posicao;
Posicao inicio, fim;
int linhas, colunas;
bool visitado[TAM_MAX][TAM_MAX];
bool podePassar(int labirinto[TAM_MAX][TAM_MAX], int linha, int coluna) {
if(labirinto[linha][coluna] == 1) return false; // Parede
else if(linha == fim.linha && coluna == fim.coluna) return true; // Chegou ao destino
else {
// Verifica todas as direções possíveis
if(linha - 1 >= 0 && !visitado[linha - 1][coluna]) {
visitado[linha - 1][coluna] = true;
if(podePassar(labirinto, linha - 1, coluna)) return true;
}
if(linha + 1 < linhas && !visitado[linha + 1][coluna]) {
visitado[linha + 1][coluna] = true;
if(podePassar(labirinto, linha + 1, coluna)) return true;
}
if(coluna - 1 >= 0 && !visitado[linha][coluna - 1]) {
visitado[linha][coluna - 1] = true;
if(podePassar(labirinto, linha, coluna - 1)) return true;
}
if(coluna + 1 < colunas && !visitado[linha][coluna + 1]) {
visitado[linha][coluna + 1] = true;
if(podePassar(labirinto, linha, coluna + 1)) return true;
}
return false;
}
}
int main() {
scanf("%d%d", &linhas, &colunas);
int labirinto[TAM_MAX][TAM_MAX];
scanf("%d%d", &inicio.linha, &inicio.coluna);
scanf("%d%d", &fim.linha, &fim.coluna);
for(int i = 0; i < linhas; i++) {
for(int j = 0; j < colunas; j++) {
scanf("%d", &labirinto[i][j]);
visitado[i][j] = false;
}
}
visitado[inicio.linha][inicio.coluna] = true;
if(podePassar(labirinto, inicio.linha, inicio.coluna)) printf("Sim");
else printf("Não");
return 0;
}
- Geração de Binários com Backtracking
Este algoritmo utiliza backtracking para gerar todas as combinações possíveis de números binários de n bits.
#include <iostream>
using namespace std;
#define TAM_MAX 20
int sequencia[TAM_MAX];
void gerarBinarios(int n, int posicao) {
if(posicao == n) {
for(int i = 0; i < n; i++) {
printf("%d", sequencia[i]);
}
printf("\n");
return;
}
sequencia[posicao] = 0;
gerarBinarios(n, posicao + 1);
sequencia[posicao] = 1;
gerarBinarios(n, posicao + 1);
}
int main() {
int n;
cin >> n;
gerarBinarios(n, 0);
return 0;
}
- Geração de Permutações com Backtracking
Implementação de backtracking para gerar todas as permutações possíveis de um conjunto de elementos.
#include <iostream>
using namespace std;
char resultado[10];
void trocar(char *c1, char *c2) {
char temp = *c2;
*c2 = *c1;
*c1 = temp;
}
void gerarPermutacoes(int n, char *str, int posicao) {
if(posicao == n) {
for(int i = 0; i < n; i++) {
cout << resultado[i];
}
cout << endl;
}
else {
for(int i = posicao; i < n; i++) {
trocar(&str[posicao], &str[i]);
resultado[posicao] = str[posicao];
gerarPermutacoes(n, str, posicao + 1);
trocar(&str[posicao], &str[i]); // Restaura a ordem original
}
}
}
int main() {
int n;
cin >> n;
char str[n];
for(int i = 0; i < n; i++) {
str[i] = 'a' + i;
}
gerarPermutacoes(n, str, 0);
return 0;
}
- Encontrar o k-ésimo Menor Elemento
Utiliza a abordagem do QuickSort para encontrar o k-ésimo menor elemento em tempo linear.
#include <iostream>
using namespace std;
void trocar(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void encontrarKesimo(int *vetor, int esquerda, int direita, int k) {
int i = esquerda, j = direita;
int pivo = vetor[esquerda];
while(i != j) {
while(i != j && vetor[j] >= pivo) j--;
vetor[i] = vetor[j];
while(i != j && vetor[i] < pivo) i++;
vetor[j] = vetor[i];
}
vetor[i] = pivo;
if(k < i) encontrarKesimo(vetor, esquerda, i - 1, k);
else if(k > i) encontrarKesimo(vetor, i + 1, direita, k);
else cout << vetor[i];
}
int main() {
int n;
cin >> n;
int vetor[n];
for(int i = 0; i < n; i++) {
cin >> vetor[i];
}
int k;
cin >> k;
encontrarKesimo(vetor, 0, n - 1, k - 1);
return 0;
}
- Máxima Soma de Subarray (Divisão e Conquista)
Implementação do algoritmo de divisão e conquista para encontrar a máxima soma de um subarray contíguo.
#include <iostream>
using namespace std;
int maximo(int a, int b, int c) {
int maior = a;
if(b > maior) maior = b;
if(c > maior) maior = c;
return maior;
}
int somaSubarrayMax(int *vetor, int esquerda, int direita) {
if(esquerda == direita) {
return vetor[esquerda];
}
int somaEsquerda, somaDireita;
int somaBordaEsquerda = -10000, somaTempEsquerda = 0;
int somaBordaDireita = -10000, somaTempDireita = 0;
int meio = (esquerda + direita) / 2;
somaEsquerda = somaSubarrayMax(vetor, esquerda, meio);
somaDireita = somaSubarrayMax(vetor, meio + 1, direita);
// Calcula a soma máxima que inclui elementos do meio para a esquerda
for(int i = meio; i >= esquerda; i--) {
somaTempEsquerda += vetor[i];
if(somaTempEsquerda > somaBordaEsquerda) somaBordaEsquerda = somaTempEsquerda;
}
// Calcula a soma máxima que inclui elementos do meio para a direita
for(int j = meio + 1; j <= direita; j++) {
somaTempDireita += vetor[j];
if(somaTempDireita > somaBordaDireita) somaBordaDireita = somaTempDireita;
}
return maximo(somaEsquerda, somaDireita, somaBordaEsquerda + somaBordaDireita);
}
int main() {
int n;
cin >> n;
int vetor[n];
for(int i = 0; i < n; i++) {
cin >> vetor[i];
}
cout << somaSubarrayMax(vetor, 0, n - 1) << endl;
return 0;
}
- Potência de Matriz (Divisão e Conquista)
Implementação eficiente para calcular a potência k de uma matriz n x n usando divisão e conquista.
#include <iostream>
using namespace std;
#define TAM_MAX 1000
#define MOD 1000000007
int dimensao;
int **multiplicarMatrizes(int **A, int **B) {
int **resultado = (int **)malloc(sizeof(int *) * dimensao);
for (int i = 0; i < dimensao; i++) {
resultado[i] = (int *)malloc(sizeof(int) * dimensao);
for (int j = 0; j < dimensao; j++) {
resultado[i][j] = 0;
for (int k = 0; k < dimensao; k++) {
resultado[i][j] = (resultado[i][j] + (A[i][k] * 1LL * B[k][j]) % MOD) % MOD;
}
}
}
return resultado;
}
int **potenciaMatriz(int **matriz, int expoente) {
if(expoente <= 1) {
return matriz;
}
int **resultado;
if(expoente % 2) resultado = multiplicarMatrizes(matriz, potenciaMatriz(matriz, expoente - 1));
else {
int **metade = potenciaMatriz(matriz, expoente / 2);
resultado = multiplicarMatrizes(metade, metade);
}
return resultado;
}
int main() {
int k;
cin >> dimensao >> k;
int **matriz = (int **)malloc(sizeof(int *) * dimensao);
// Inicialização da matriz
for(int i = 0; i < dimensao; i++) {
matriz[i] = (int *)malloc(sizeof(int) * dimensao);
for(int j = 0; j < dimensao; j++) {
cin >> matriz[i][j];
}
}
matriz = potenciaMatriz(matriz, k);
for(int i = 0; i < dimensao; i++) {
for(int j = 0; j < dimensao; j++) {
cout << matriz[i][j] << " ";
}
cout << endl;
}
return 0;
}
- Problema da Mochila 0/1 (Backtracking)
Solução utilizando backtracking para o problema clássico da mochila 0/1.
#include <iostream>
using namespace std;
#define TAM_MAX 100
int pesos[TAM_MAX];
int valores[TAM_MAX];
int valorMaximo = 0;
int valorAtual = 0;
int selecionado[TAM_MAX];
int solucao[TAM_MAX];
int nItens;
void resolverMochila(int item, int capacidadeRestante) {
if (item == nItens) {
if (valorAtual > valorMaximo) {
valorMaximo = valorAtual;
for (int i = 0; i < nItens; i++) {
solucao[i] = selecionado[i];
}
}
return;
}
// Tentativa de incluir o item atual
if (pesos[item] <= capacidadeRestante) {
selecionado[item] = 1;
valorAtual += valores[item];
resolverMochila(item + 1, capacidadeRestante - pesos[item]);
// Backtrack
valorAtual -= valores[item];
selecionado[item] = 0;
}
// Tentativa de não incluir o item atual
resolverMochila(item + 1, capacidadeRestante);
}
int main() {
cout << "Digite o número de itens: " << endl;
cin >> nItens;
cout << "Digite o peso e valor de cada item: " << endl;
for (int i = 0; i < nItens; i++) {
cin >> pesos[i] >> valores[i];
}
cout << "Digite a capacidade da mochila: " << endl;
int capacidade;
cin >> capacidade;
resolverMochila(0, capacidade);
cout << "Valor máximo: " << valorMaximo << endl;
cout << "Itens selecionados: ";
for (int i = 0; i < nItens; i++) {
cout << solucao[i] << " ";
}
cout << endl;
return 0;
}
- Problema das Fortalezas (Backtracking)
Posicionamento de fortalezas em um tabuleiro de forma que não se ataquem mutuamente.
#include <iostream>
using namespace std;
int tamanho;
int tabuleiro[4][4]; // 0=vazio, 1=parede, 2=fortaleza
int original[4][4];
int contador = 0;
int maximo = 0;
int resultados[20];
bool podeColocar(int linha, int coluna) {
// Verifica verticalmente
for(int i = linha; i >= 0; i--) {
if(tabuleiro[i][coluna] == 2) return false;
if(tabuleiro[i][coluna] == 1) break;
}
for(int i = linha; i < tamanho; i++) {
if(tabuleiro[i][coluna] == 2) return false;
if(tabuleiro[i][coluna] == 1) break;
}
// Verifica horizontalmente
for(int j = coluna; j >= 0; j--) {
if(tabuleiro[linha][j] == 2) return false;
if(tabuleiro[linha][j] == 1) break;
}
for(int j = coluna; j < tamanho; j++) {
if(tabuleiro[linha][j] == 2) return false;
if(tabuleiro[linha][j] == 1) break;
}
return true;
}
void backtracking(int linha, int coluna) {
if(coluna == tamanho) {
linha++;
coluna = 0;
}
if(linha == tamanho) {
if(maximo < contador) {
maximo = contador;
}
return;
}
if(podeColocar(linha, coluna) && !original[linha][coluna]) {
contador++;
tabuleiro[linha][coluna] = 2;
backtracking(linha, coluna + 1);
contador--;
tabuleiro[linha][coluna] = original[linha][coluna];
}
backtracking(linha, coluna + 1);
}
int main() {
int casos = 0;
while(1) {
cin >> tamanho;
if(!tamanho) break;
char c;
contador = 0;
maximo = 0;
for(int i = 0; i < tamanho; i++) {
for(int j = 0; j < tamanho; j++) {
cin >> c;
if(c == '.') tabuleiro[i][j] = 0;
else tabuleiro[i][j] = 1;
original[i][j] = tabuleiro[i][j];
}
}
backtracking(0, 0);
resultados[casos++] = maximo;
}
for(int i = 0; i < casos; i++) {
cout << resultados[i] << endl;
}
return 0;
}
- Problema das N-Rainhas (Backtracking)
Implementação clássica do problema das N-Rainhas utilizando backtracking.
#include <iostream>
using namespace std;
#define N 8
char tabuleiro[N][N];
int solucoes = 1;
bool posicaoValida(int linha, int coluna) {
// Verifica verticalmente
for(int i = linha; i >= 0; i--) {
if(tabuleiro[i][coluna] == 'R') return false;
}
// Verifica diagonal superior esquerda
for(int i = linha, j = coluna; i >= 0 && j >= 0; i--, j--) {
if(tabuleiro[i][j] == 'R') return false;
}
// Verifica diagonal superior direita
for(int i = linha, j = coluna; i >= 0 && j < N; i--, j++) {
if(tabuleiro[i][j] == 'R') return false;
}
return true;
}
void resolverRainhas(int rainha) {
if(rainha == N) {
cout << "Solução " << solucoes++ << ":" << endl;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cout << tabuleiro[i][j];
}
cout << endl;
}
return;
}
for(int j = 0; j < N; j++) {
if(posicaoValida(rainha, j)) {
tabuleiro[rainha][j] = 'R';
}
else continue;
resolverRainhas(rainha + 1);
// Backtrack
tabuleiro[rainha][j] = '.';
}
}
int main() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
tabuleiro[i][j] = '.';
}
}
resolverRainhas(0);
return 0;
}
- Problema do Labirinto (BFS)
Solução para encontrar um caminho em um labirinto utilizando Busca em Largura (BFS).
#include <iostream>
#include <queue>
using namespace std;
typedef struct No {
int x, y;
} Posicao;
Posicao fila[400];
int frente = 0, tras = 0;
char labirinto[20][20];
int inicioX, inicioY, fimX, fimY;
bool resultados[10];
int contador = 0;
int direcoes[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // Cima, Baixo, Esquerda, Direita
bool bfs(int x, int y) {
frente = tras = 0;
fila[tras].x = x;
fila[tras].y = y;
tras++;
labirinto[x][y] = 'X'; // Marca como visitado
while(frente < tras) {
Posicao atual = fila[frente++];
if(atual.x == fimX && atual.y == fimY) {
return true;
}
// Explora as quatro direções
for(int i = 0; i < 4; i++) {
int novoX = atual.x + direcoes[i][0];
int novoY = atual.y + direcoes[i][1];
if(novoX >= 0 && novoX < 20 && novoY >= 0 && novoY < 20 && labirinto[novoX][novoY] == '.') {
labirinto[novoX][novoY] = 'X';
fila[tras].x = novoX;
fila[tras].y = novoY;
tras++;
}
}
}
return false;
}
int main() {
int casos;
cin >> casos;
for(int i = 0; i < casos; i++) {
cin >> inicioX >> inicioY >> fimX >> fimY;
resultados[contador] = false;
for(int j = 0; j < 20; j++) {
for(int k = 0; k < 20; k++) {
cin >> labirinto[j][k];
}
}
resultados[contador] = bfs(inicioX, inicioY);
contador++;
}
for(int i = 0; i < contador; i++) {
if(resultados[i]) cout << "Sim" << endl;
else cout << "Não" << endl;
}
return 0;
}
- Transformação de Cadeias (Backtracking)
Algoritmo para gerar todas as sequências de operações para transformar uma string em outra usando uma pilha.
#include <iostream>
#include <cstring>
using namespace std;
char origem[20], destino[20];
char pilha[20];
int topoPilha = 0;
int posOrigem = 0;
int posDestino = 0;
int tamanho;
char operacoes[100];
int topoOperacoes = 0;
void empilhar(char c) {
pilha[topoPilha++] = c;
}
void desempilhar() {
if(topoPilha > 0) topoPilha--;
}
void dfs() {
if(posDestino == tamanho) {
for(int i = 0; i < topoOperacoes - 1; i++) {
cout << operacoes[i] << " ";
}
cout << operacoes[topoOperacoes - 1] << endl;
return;
}
if(posOrigem < tamanho) {
// Operação de empilhar
operacoes[topoOperacoes++] = 'i';
empilhar(origem[posOrigem++]);
dfs();
// Backtrack
topoOperacoes--;
posOrigem--;
desempilhar();
}
// Operação de desempilhar
if(topoPilha > 0 && pilha[topoPilha - 1] == destino[posDestino]) {
operacoes[topoOperacoes++] = 'o';
posDestino++;
desempilhar();
dfs();
// Backtrack
posDestino--;
topoOperacoes--;
empilhar(destino[posDestino]);
}
}
int main() {
while(cin >> origem >> destino) {
tamanho = strlen(origem);
cout << "[" << endl;
dfs();
cout << "]" << endl;
}
return 0;
}
- Problema de Irrigação de Fazendas (DFS)
Utiliza DFS para contar o número de campos conectados em uma fazenda representada por diferentes tipos de terrenos.
#include <iostream>
using namespace std;
typedef struct campo {
char tipo;
int visitado;
int norte, sul, oeste, leste;
} Terreno;
Terreno fazenda[50][50];
int linhas, colunas;
void dfs(int linha, int coluna) {
fazenda[linha][coluna].visitado = 1;
// Verifica conexão para o norte
if(linha > 0 && !fazenda[linha-1][coluna].visitado &&
(fazenda[linha-1][coluna].sul && fazenda[linha][coluna].norte)) {
dfs(linha-1, coluna);
}
// Verifica conexão para o sul
if(linha < linhas-1 && !fazenda[linha+1][coluna].visitado &&
(fazenda[linha+1][coluna].norte && fazenda[linha][coluna].sul)) {
dfs(linha+1, coluna);
}
// Verifica conexão para o oeste
if(coluna > 0 && !fazenda[linha][coluna-1].visitado &&
(fazenda[linha][coluna-1].leste && fazenda[linha][coluna].oeste)) {
dfs(linha, coluna-1);
}
// Verifica conexão para o leste
if(coluna < colunas-1 && !fazenda[linha][coluna+1].visitado &&
(fazenda[linha][coluna+1].oeste && fazenda[linha][coluna].leste)) {
dfs(linha, coluna+1);
}
return;
}
int main() {
int campos;
while(1) {
campos = 0;
cin >> linhas >> colunas;
if(linhas == -1 && colunas == -1) break;
for(int i = 0; i < linhas; i++) {
for(int j = 0; j < colunas; j++) {
cin >> fazenda[i][j].tipo;
// Inicialização
fazenda[i][j].visitado = 0;
fazenda[i][j].norte = fazenda[i][j].sul = 0;
fazenda[i][j].oeste = fazenda[i][j].leste = 0;
// Configura as conexões baseado no tipo de terreno
if(fazenda[i][j].tipo == 'A')
fazenda[i][j].norte = fazenda[i][j].oeste = 1;
else if(fazenda[i][j].tipo == 'B')
fazenda[i][j].norte = fazenda[i][j].leste = 1;
else if(fazenda[i][j].tipo == 'C')
fazenda[i][j].oeste = fazenda[i][j].sul = 1;
else if(fazenda[i][j].tipo == 'D')
fazenda[i][j].leste = fazenda[i][j].sul = 1;
else if(fazenda[i][j].tipo == 'E')
fazenda[i][j].sul = fazenda[i][j].norte = 1;
else if(fazenda[i][j].tipo == 'F')
fazenda[i][j].leste = fazenda[i][j].oeste = 1;
else if(fazenda[i][j].tipo == 'G')
fazenda[i][j].leste = fazenda[i][j].oeste = fazenda[i][j].norte = 1;
else if(fazenda[i][j].tipo == 'H')
fazenda[i][j].norte = fazenda[i][j].sul = fazenda[i][j].oeste = 1;
else if(fazenda[i][j].tipo == 'I')
fazenda[i][j].oeste = fazenda[i][j].leste = fazenda[i][j].sul = 1;
else if(fazenda[i][j].tipo == 'J')
fazenda[i][j].norte = fazenda[i][j].sul = fazenda[i][j].leste = 1;
else if(fazenda[i][j].tipo == 'K')
fazenda[i][j].norte = fazenda[i][j].sul = fazenda[i][j].leste = fazenda[i][j].oeste = 1;
}
}
for(int i = 0; i < linhas; i++) {
for(int j = 0; j < colunas; j++) {
if(!fazenda[i][j].visitado) {
dfs(i, j);
campos++;
}
}
}
cout << campos << endl;
}
return 0;
}
- Cálculo do Perímetro de uma Imagem (DFS)
Utiliza DFS para calcular o perímetro de uma região em uma imagem binária.
#include <iostream>
using namespace std;
int direcoes[8][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}, {-1,-1}, {-1,1}, {1,-1}, {1,1}};
char imagem[50][50];
int perimetro = 0;
int visitado[50][50];
int linhas, colunas, inicioX, inicioY;
void dfs(int x, int y) {
visitado[x][y] = 1;
int novoX, novoY;
for(int i = 0; i < 8; i++) {
novoX = x + direcoes[i][0];
novoY = y + direcoes[i][1];
if(novoX < 0 || novoX == linhas || novoY < 0 || novoY == colunas) {
if(i < 4) perimetro++; // Apenas direções cardinais
continue;
}
if(imagem[novoX][novoY] == '.') {
if(i < 4) perimetro++; // Apenas direções cardinais
continue;
}
if(!visitado[novoX][novoY]) dfs(novoX, novoY);
}
}
int main() {
while(1) {
perimetro = 0;
cin >> linhas >> colunas >> inicioX >> inicioY;
if(!inicioX && !inicioY && !linhas && !colunas) break;
for(int i = 0; i < linhas; i++) {
for(int j = 0; j < colunas; j++) {
visitado[i][j] = 0;
cin >> imagem[i][j];
}
}
dfs(inicioX-1, inicioY-1);
cout << perimetro << endl;
}
return 0;
}
- Problema de Coloração de Grafos (m-coloração)
Utiliza backtracking para determinar o número de maneiras de colorir um grafo com m cores.
#include <iostream>
using namespace std;
int vertices, arestas, cores;
int corVertice[20] = {0}; // 0=não colorido, 1..m=cores
int matrizAdj[20][20]; // Matriz de adjacência
int solucoes = 0;
bool corValida(int vertice) {
// Verifica se a cor do vértice atual é diferente de todos os vértices adjacentes já coloridos
for(int i = 0; i < vertice; i++) {
if(matrizAdj[i][vertice] && corVertice[i] == corVertice[vertice])
return false;
}
return true;
}
void dfs(int vertice) {
if(vertice == vertices) {
solucoes++;
return;
}
else {
for(int i = 1; i <= cores; i++) {
corVertice[vertice] = i;
if(corValida(vertice)) {
dfs(vertice + 1);
}
// Backtrack
corVertice[vertice] = 0;
}
}
}
int main() {
cin >> vertices >> arestas >> cores;
int u, v;
for(int i = 0; i < arestas; i++) {
cin >> u >> v;
matrizAdj[u][v] = 1;
matrizAdj[v][u] = 1;
}
dfs(0);
cout << solucoes << endl;
return 0;
}
- Problema do Cavalo Saltitante (BFS)
Utiliza BFS para encontrar o caminho mínimo para um cavalo de xadrez alcançar uma posição específica.
#include <iostream>
#include <queue>
using namespace std;
typedef struct No {
int x, y;
int passos;
int cor; // R-0 Y-1 B-2 W-3 G-4
int direcao;
} Estado;
char tabuleiro[20][20];
int visitado[20][20][5][4] = {0};
void converterCor(Estado *e, char cor) {
if(cor == 'R') e->cor = 0;
else if(cor == 'Y') e->cor = 1;
else if(cor == 'B') e->cor = 2;
else if(cor == 'W') e->cor = 3;
else if(cor == 'G') e->cor = 4;
}
void converterDirecao(Estado *e, char dir) {
if(dir == 'E') e->direcao = 0; // Leste
else if(dir == 'S') e->direcao = 1; // Sul
else if(dir == 'W') e->direcao = 2; // Oeste
else if(dir == 'N') e->direcao = 3; // Norte
}
int main() {
Estado inicio, destino;
char corInicio, corDestino, dirInicio;
cin >> inicio.x >> inicio.y >> corInicio >> dirInicio >> destino.x >> destino.y >> corDestino;
inicio.x--; inicio.y--; destino.x--; destino.y--;
inicio.passos = 0;
converterCor(&inicio, corInicio);
converterCor(&destino, corDestino);
converterDirecao(&inicio, dirInicio);
for(int i = 0; i < 20; i++) {
for(int j = 0; j < 20; j++) {
cin >> tabuleiro[i][j];
}
}
queue<Estado> q;
q.push(inicio);
visitado[inicio.x][inicio.y][inicio.cor][inicio.direcao] = 1;
while(!q.empty()) {
Estado atual = q.front();
q.pop();
if(atual.cor == destino.cor && atual.x == destino.x && atual.y == destino.y) {
cout << atual.passos;
return 0;
}
Estado novo;
// Gira para a esquerda
novo = atual;
novo.direcao = (atual.direcao + 1) % 4;
novo.passos += 1;
if(novo.x >= 0 && novo.x < 20 && novo.y >= 0 && novo.y < 20 &&
!visitado[novo.x][novo.y][novo.cor][novo.direcao]) {
q.push(novo);
visitado[novo.x][novo.y][novo.cor][novo.direcao] = 1;
}
// Gira para a direita
novo = atual;
novo.direcao = (atual.direcao - 1 + 4) % 4;
novo.passos += 1;
if(novo.x >= 0 && novo.x < 20 && novo.y >= 0 && novo.y < 20 &&
!visitado[novo.x][novo.y][novo.cor][novo.direcao]) {
q.push(novo);
visitado[novo.x][novo.y][novo.cor][novo.direcao] = 1;
}
// Move para a frente
if(atual.direcao == 0) { // Leste
novo = atual;
novo.cor = (novo.cor + 1) % 5;
novo.y += 1;
novo.passos += 1;
if (tabuleiro[novo.x][novo.y] == '.' &&
!visitado[novo.x][novo.y][novo.cor][novo.direcao] &&
novo.x >= 0 && novo.x < 20 && novo.y >= 0 && novo.y < 20) {
q.push(novo);
visitado[novo.x][novo.y][novo.cor][novo.direcao] = 1;
}
}
else if(atual.direcao == 1) { // Sul
novo = atual;
novo.cor = (novo.cor + 1) % 5;
novo.x += 1;
novo.passos += 1;
if (tabuleiro[novo.x][novo.y] == '.' &&
!visitado[novo.x][novo.y][novo.cor][novo.direcao] &&
novo.x >= 0 && novo.x < 20 && novo.y >= 0 && novo.y < 20) {
q.push(novo);
visitado[novo.x][novo.y][novo.cor][novo.direcao] = 1;
}
}
else if(atual.direcao == 2) { // Oeste
novo = atual;
novo.cor = (novo.cor + 1) % 5;
novo.y -= 1;
novo.passos += 1;
if(tabuleiro[novo.x][novo.y] == '.' &&
!visitado[novo.x][novo.y][novo.cor][novo.direcao] &&
novo.x >= 0 && novo.x < 20 && novo.y >= 0 && novo.y < 20) {
q.push(novo);
visitado[novo.x][novo.y][novo.cor][novo.direcao] = 1;
}
}
else if(atual.direcao == 3) { // Norte
novo = atual;
novo.cor = (novo.cor + 1) % 5;
novo.x -= 1;
novo.passos += 1;
if(tabuleiro[novo.x][novo.y] == '.' &&
!visitado[novo.x][novo.y][novo.cor][novo.direcao] &&
novo.x >= 0 && novo.x < 20 && novo.y >= 0 && novo.y < 20) {
q.push(novo);
visitado[novo.x][novo.y][novo.cor][novo.direcao] = 1;
}
}
}
return 0;
}
- Problema dos Seis Dígitos (BFS com STL)
Utiliza BFS e contêineres STL para resolver um quebra-cabeça de transformação de números.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<vector<int>> visitados;
vector<int> operacaoA(vector<int> estado) {
vector<int> novoEstado(6, 0);
novoEstado[0] = estado[1];
novoEstado[1] = estado[4];
novoEstado[4] = estado[3];
novoEstado[3] = estado[0];
novoEstado[2] = estado[2];
novoEstado[5] = estado[5];
return novoEstado;
}
vector<int> operacaoB(vector<int> estado) {
vector<int> novoEstado(6);
novoEstado[1] = estado[2];
novoEstado[2] = estado[5];
novoEstado[5] = estado[4];
novoEstado[4] = estado[1];
novoEstado[0] = estado[0];
novoEstado[3] = estado[3];
return novoEstado;
}
bool estadoVisitado(vector<int> estado) {
for(auto i = visitados.begin(); i != visitados.end(); ++i) {
if(estado == *i) return false;
}
return true;
}
int main() {
vector<int> estado(6);
vector<int> alvo = {1, 2, 3, 4, 5, 6};
while(cin >> estado[0] >> estado[1] >> estado[2] >> estado[3] >> estado[4] >> estado[5]) {
queue<vector<int>> q;
visitados.clear();
bool encontrado = false;
q.push(estado);
while(!q.empty()) {
vector<int> atual = q.front();
q.pop();
if(atual == alvo) {
encontrado = true;
break;
}
vector<int> novoEstado;
novoEstado = operacaoA(atual);
if(estadoVisitado(novoEstado)) {
q.push(novoEstado);
visitados.push_back(novoEstado);
}
novoEstado = operacaoB(atual);
if(estadoVisitado(novoEstado)) {
q.push(novoEstado);
visitados.push_back(novoEstado);
}
}
if(encontrado) cout << "Sim" << endl;
else cout << "Não" << endl;
}
return 0;
}
- Problema de Despejo de Água (BFS)
Utiliza BFS para resolver o problema clássico de despejar água entre recipientes para obter uma medida específica.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef struct recipiente {
int capacidade;
int atual;
} Jarra;
typedef struct Estado {
int jarraA;
int jarraB;
int jarraC;
int passos;
} EstadoAgua;
int capA, capB, capC;
vector<EstadoAgua> estadosVisitados;
void despejar(int &origem, int &destino, int capDestino) {
if(origem + destino <= capDestino) {
destino = origem + destino;
origem = 0;
}
else {
int temp = capDestino - destino;
destino = capDestino;
origem = origem - temp;
}
}
bool estadoNovo(EstadoAgua estado) {
for(auto i = estadosVisitados.begin(); i != estadosVisitados.end(); i++) {
if((*i).jarraA == estado.jarraA && (*i).jarraB == estado.jarraB && (*i).jarraC == estado.jarraC)
return false;
}
return true;
}
int main() {
cin >> capA >> capB >> capC;
EstadoAgua inicio = {capA, 0, 0, 0};
queue<EstadoAgua> q;
q.push(inicio);
estadosVisitados.push_back(inicio);
while(!q.empty()) {
EstadoAgua atual = q.front();
q.pop();
// Verifica se encontramos a solução (duas jarras com metade da capacidade)
if((atual.jarraB == capA/2 || atual.jarraC == capA/2) && atual.jarraA == capA/2) {
cout << atual.passos;
return 0;
}
// Despejar da jarra A para B
if(atual.jarraA) {
EstadoAgua novoEstado = atual;
despejar(novoEstado.jarraA, novoEstado.jarraB, capB);
novoEstado.passos++;
if(estadoNovo(novoEstado)) {
q.push(novoEstado);
estadosVisitados.push_back(novoEstado);
}
// Despejar da jarra A para C
novoEstado = atual;
despejar(novoEstado.jarraA, novoEstado.jarraC, capC);
novoEstado.passos++;
if(estadoNovo(novoEstado)) {
q.push(novoEstado);
estadosVisitados.push_back(novoEstado);
}
}
// Despejar da jarra B para A
if(atual.jarraB) {
EstadoAgua novoEstado = atual;
despejar(novoEstado.jarraB, novoEstado.jarraA, capA);
novoEstado.passos++;
if(estadoNovo(novoEstado)) {
q.push(novoEstado);
estadosVisitados.push_back(novoEstado);
}
// Despejar da jarra B para C
novoEstado = atual;
despejar(novoEstado.jarraB, novoEstado.jarraC, capC);
novoEstado.passos++;
if(estadoNovo(novoEstado)) {
q.push(novoEstado);
estadosVisitados.push_back(novoEstado);
}
}
// Despejar da jarra C para A
if(atual.jarraC) {
EstadoAgua novoEstado = atual;
despejar(novoEstado.jarraC, novoEstado.jarraA, capA);
novoEstado.passos++;
if(estadoNovo(novoEstado)) {
q.push(novoEstado);
estadosVisitados.push_back(novoEstado);
}
// Despejar da jarra C para B
novoEstado = atual;
despejar(novoEstado.jarraC, novoEstado.jarraB, capB);
novoEstado.passos++;
if(estadoNovo(novoEstado)) {
q.push(novoEstado);
estadosVisitados.push_back(novoEstado);
}
}
}
return 0;
}
- Problema de Fusão de Pedras (Programação Dinâmica)
Solução utilizanod programação dinâmica para o problema de fusão de pedras em um arranjo circular.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1 << 30;
// Calcula a soma de elementos em um intervalo circular
int somaIntervalo(const vector<int>& somaPrefixa, int inicio, int comprimento, int n) {
if(inicio + comprimento >= n)
return somaIntervalo(somaPrefixa, inicio, n - inicio - 1, n) +
somaIntervalo(somaPrefixa, 0, (inicio + comprimento) % n, n);
else
return somaPrefixa[inicio + comprimento] - (inicio > 0 ? somaPrefixa[inicio - 1] : 0);
}
int calcularMinimo(const vector<int>& pedras, int n) {
vector<vector<int>> minimos(n, vector<int>(n, INF));
// Inicialização para intervalos de comprimento 0
for(int i = 0; i < n; i++)
minimos[i][0] = 0;
// Cálculo para todos os comprimentos de intervalo
for(int comprimento = 1; comprimento < n; comprimento++) {
for(int i = 0; i < n; i++) {
// Tenta todos os pontos de divisão possíveis
for(int k = 0; k < comprimento; k++) {
minimos[i][comprimento] = min(minimos[i][comprimento],
minimos[i][k] +
minimos[(i + k + 1) % n][comprimento - k - 1] +
somaIntervalo(pedras, i, comprimento, n));
}
}
}
// Encontra o valor mínimo entre todos os intervalos de tamanho n
int valorMinimo = minimos[0][n - 1];
for(int i = 1; i < n; i++) {
valorMinimo = min(valorMinimo, minimos[i][n - 1]);
}
return valorMinimo;
}
int main() {
int n;
while(cin >> n) {
if(!n) return 0;
vector<int> pedras(n);
vector<int> somaPrefixa(n);
for(int i = 0; i < n; i++) {
cin >> pedras[i];
}
// Cálculo da soma prefixa
somaPrefixa[0] = pedras[0];
for(int i = 1; i < n; i++) {
somaPrefixa[i] = somaPrefixa[i - 1] + pedras[i];
}
int resultado = calcularMinimo(somaPrefixa, n);
cout << resultado << endl;
}
return 0;
}
- Esqui (DP com Busca Memorizada)
Utiliza programação dinâmica com busca memorizada para encontrar o caminho mais longo em uma matriz de alturas.
#include <iostream>
#include <vector>
#define MAX 100000
using namespace std;
int linhas, colunas;
int alturas[100][100];
int direcoes[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
int dp[100][100];
int visitado[100][100] = {0};
typedef struct no {
int x;
int y;
int altura;
} Ponto;
Ponto pontoAtual;
bool encontrarPontoMaisBaixo() {
pontoAtual = {0, 0, 0};
int minAltura = MAX;
int minX, minY;
// Encontra o ponto não visitado com menor altitude
for(int i = 0; i < linhas; i++) {
for(int j = 0; j < colunas; j++) {
if(!visitado[i][j] && minAltura > alturas[i][j]) {
minAltura = alturas[i][j];
minX = i;
minY = j;
}
}
}
if(minAltura == MAX) {
return false;
}
visitado[minX][minY] = 1;
pontoAtual = {minX, minY, minAltura};
return true;
}
bool podeDeslizar(int dx, int dy) {
int novoX = pontoAtual.x + dx;
int novoY = pontoAtual.y + dy;
if(novoX < 0 || novoX >= linhas || novoY < 0 || novoY >= colunas) {
return false; // Fora dos limites
}
if(!visitado[novoX][novoY]) {
return false; // Ainda não visitado
}
if(alturas[pontoAtual.x][pontoAtual.y] <= alturas[novoX][novoY]) {
return false; // Não pode deslizar para cima
}
return true;
}
int main() {
cin >> linhas >> colunas;
for(int i = 0; i < linhas; i++) {
for(int j = 0; j < colunas; j++) {
cin >> alturas[i][j];
dp[i][j] = 1; // O caminho mínimo é 1 (o próprio ponto)
}
}
int resultado = 1;
while(encontrarPontoMaisBaixo()) {
// Verifica todas as direções possíveis
for(int i = 0; i < 4; i++) {
if(podeDeslizar(direcoes[i][0], direcoes[i][1])) {
if(dp[pontoAtual.x][pontoAtual.y] < dp[pontoAtual.x + direcoes[i][0]][pontoAtual.y + direcoes[i][1]] + 1) {
dp[pontoAtual.x][pontoAtual.y] = dp[pontoAtual.x + direcoes[i][0]][pontoAtual.y + direcoes[i][1]] + 1;
resultado = max(resultado, dp[pontoAtual.x][pontoAtual.y]);
}
}
}
}
cout << resultado << endl;
return 0;
}
- Máxima Soma de Subarray Contíguo (Programação Dinâmica)
Implementação do algoritmo de Kadane para encontrar a máxima soma de um subarray contíguo.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int vetor[n];
for(int i = 0; i < n; i++) {
cin >> vetor[i];
}
int dp[n], maximo = vetor[0]; // dp[i] = máxima soma terminando em i
dp[0] = vetor[0];
for(int i = 1; i < n; i++) {
dp[i] = max(dp[i-1] + vetor[i], vetor[i]);
maximo = max(dp[i], maximo);
}
cout << maximo;
return 0;
}
- Problema de Seleção de Atividades (Algoritmo Guloso)
Implementação do algoritmo guloso para selecionar o máximo número de atividades não sobrepostas.
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct {
int inicio;
int fim;
} Atividade;
// Função de comparação para ordenar atividades pelo tempo de término
bool compararAtividades(Atividade a1, Atividade a2) {
return (a1.fim < a2.fim);
}
int maximizarAtividades(Atividade atividades[], int n) {
// Ordena as atividades pelo tempo de término
sort(atividades, atividades + n, compararAtividades);
int contador = 1; // A primeira atividade sempre é selecionada
int ultimoFim = atividades[0].fim;
// Verifica as atividades restantes
for (int i = 1; i < n; i++) {
// Se o início desta atividade for maior ou igual ao fim da última selecionada
if (atividades[i].inicio >= ultimoFim) {
contador++;
ultimoFim = atividades[i].fim;
}
}
return contador;
}
int main() {
Atividade atividades[] = {{1, 3}, {2, 5}, {4, 6}, {6, 8}, {5, 7}, {8, 9}};
int n = sizeof(atividades) / sizeof(atividades[0]);
cout << "Número máximo de atividades: " << maximizarAtividades(atividades, n) << endl;
return 0;
}
- Problema de Agendamento de Tarefas (Algoritmo Guloso)
Implementação de um algoritmo guloso para minimizar o tempo máximo de conclusão em múltiplas máquinas.
#include <iostream>
#include <algorithm>
using namespace std;
// Função de comparação para ordenar em ordem decrescente
bool compararTarefas(const int& a, const int& b) {
return a > b;
}
int agendarTarefas(int* tempos, int nTarefas, int nMaquinas) {
// Ordena as tarefas em ordem decrescente de tempo de processamento
sort(tempos, tempos + nTarefas, compararTarefas);
// Inicializa as máquinas com carga zero
int* cargaMaquinas = new int[nMaquinas];
for (int i = 0; i < nMaquinas; ++i) {
cargaMaquinas[i] = 0;
}
// Aloca cada tarefa à máquina com menor carga atual
for (int i = 0; i < nTarefas; ++i) {
// Encontra a máquina com menor carga
int maquinaMinCarga = 0;
for (int j = 1; j < nMaquinas; ++j) {
if (cargaMaquinas[j] < cargaMaquinas[maquinaMinCarga]) {
maquinaMinCarga = j;
}
}
// Aloca a tarefa atual à máquina selecionada
cargaMaquinas[maquinaMinCarga] += tempos[i];
}
// Encontra a carga máxima (tempo de conclusão)
int tempoMaximo = 0;
for (int i = 0; i < nMaquinas; ++i) {
if (cargaMaquinas[i] > tempoMaximo) {
tempoMaximo = cargaMaquinas[i];
}
}
delete[] cargaMaquinas;
return tempoMaximo;
}
int main() {
int tempos[] = {3, 6, 4, 7, 2}; // Tempos de processamento das tarefas
int nTarefas = sizeof(tempos) / sizeof(tempos[0]);
int nMaquinas = 2; // Número de máquinas
int resultado = agendarTarefas(tempos, nTarefas, nMaquinas);
cout << "Tempo máximo de conclusão: " << resultado << endl;
return 0;
}