Busca em Profundidade sem Backtracking para Acessibilidade

Em problemas de labirinto onde o objetivo é apenas verificar a existência de um caminho entre dois pontos, não é necessário restaurar o estado dos nós visitados. Utilizar uma abordagem de DFS que marca permanentemente as células visitadas evita a reexploração desnecessária. Isso reduz a complexidade de tempo exponencial para linear em relação ao tamanho do grid, O(N*M), impedindo que o algoritmo exceda o limite de tempo.

A implementação abaixo modifica o grid original para marcar as posições já processadas, eliminando a necessidade de uma matriz de visitados separada e do passo de backtracking.

#include<iostream>
#include<vector>
using namespace std;

int linhas, colunas;
vector<string> grid;
bool alcançado = false;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void navegar(int x, int y) {
    if (x == linhas && y == colunas) {
        alcançado = true;
        return;
    }
    
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx >= 1 && nx <= linhas && ny >= 1 && ny <= colunas) {
            if (grid[nx][ny] == '.') {
                grid[nx][ny] = '#'; // Marca como visitado permanentemente
                navegar(nx, ny);
                if (alcançado) return;
            }
        }
    }
}

int main() {
    cin >> linhas >> colunas;
    grid.resize(linhas + 1);
    for (int i = 1; i <= linhas; ++i) {
        string linha;
        cin >> linha;
        grid[i] = " " + linha; // Índice 1-based
    }
    
    grid[1][1] = '#';
    navegar(1, 1);
    
    if (alcançado) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

Geração de Permutações via Recursão

Para listar todas as permutações possíveis de uma sequência numérica, pode-se utilizar uma função recursiva que constrói a solução passo a passo. Um vetor de controle indica quais números já foram utilizados na ramiifcação atual. Embora exista uma função nativa na biblioteca padrão, implementar a lógica manualmente demonstra o entendimento do mecanismo de backtracking.

#include<iostream>
#include<iomanip>
#include<vector>
using namespace std;

int n;
vector<int> resultado;
vector<bool> ocupado;

void gerarPermutacoes(int indice) {
    if (indice > n) {
        for (int i = 1; i <= n; ++i) {
            cout << setw(5) << resultado[i];
        }
        cout << endl;
        return;
    }
    
    for (int i = 1; i <= n; ++i) {
        if (!ocupado[i]) {
            ocupado[i] = true;
            resultado[indice] = i;
            gerarPermutacoes(indice + 1);
            ocupado[i] = false; // Backtracking
        }
    }
}

int main() {
    cin >> n;
    resultado.resize(n + 1);
    ocupado.assign(n + 1, false);
    gerarPermutacoes(1);
    return 0;
}

Contagem de Componentes Conectados em Grid

Este problema equivale a contar regiões conectadas em uma matriz bidimensional. A estratégia envolve iterar sobre cada célula e, ao encontrar um valor não nulo não visitado, iniciar uma DFS para marcar toda a região conectada como visitada. Cada iniciação representa um novo componente encontrado.

É crucial converter a entrada de caracteres para valores inteiros para facilitar a verificação lógica durante a travessia.

#include<iostream>
#include<cstring>
using namespace std;

int n, m, totalComponentes = 0;
int campo[105][105];
bool visitado[105][105];
int movX[] = {0, 0, 1, -1};
int movY[] = {1, -1, 0, 0};

void expandirCelula(int x, int y) {
    visitado[x][y] = true;
    for (int i = 0; i < 4; ++i) {
        int nx = x + movX[i];
        int ny = y + movY[i];
        
        if (nx > 0 && nx <= n && ny > 0 && ny <= m) {
            if (!visitado[nx][ny] && campo[nx][ny] != 0) {
                expandirCelula(nx, ny);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(visitado, 0, sizeof(visitado));
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char temp;
            cin >> temp;
            campo[i][j] = temp - '0';
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (!visitado[i][j] && campo[i][j] != 0) {
                expandirCelula(i, j);
                totalComponentes++;
            }
        }
    }
    
    cout << totalComponentes << endl;
    return 0;
}

Problema das N-Rainhas com Otimização de Diagonais

A solução clássica para o problema das N-Rainhas requer verificação de conflitos em linhas, colunas e diagonais. Para otimizar a verificação de diagonais, utiliza-se a propriedade matemática onde células na mesma diagonal principal possuem diferença constante (linha - coluna) e células na mesma diagonal secundária possuem soma constante (linha + coluna).

Arrays booleanos são utilizados para marcar essas somas e diferenças, permitindo verificação em O(1) durante a recursão. Atenção especial deve ser dada aos índices dos arrays de diagonais para evitar acesso fora dos limites.

#include<iostream>
#include<vector>
using namespace std;

int n;
bool diagNeg[50], diagPos[50], linha[50];
vector<int> solucao;
int totalSolucoes = 0;
int exibirLimite = 3;

void posicionarRainha(int col) {
    if (col > n) {
        if (exibirLimite > 0) {
            for (int i = 1; i <= n; ++i) {
                cout << solucao[i] << " ";
            }
            cout << endl;
            exibirLimite--;
        }
        totalSolucoes++;
        return;
    }
    
    for (int r = 1; r <= n; ++r) {
        if (!linha[r] && !diagNeg[col - r + n] && !diagPos[col + r]) {
            linha[r] = true;
            diagNeg[col - r + n] = true;
            diagPos[col + r] = true;
            solucao[col] = r;
            
            posicionarRainha(col + 1);
            
            linha[r] = false;
            diagNeg[col - r + n] = false;
            diagPos[col + r] = false;
        }
    }
}

int main() {
    cin >> n;
    solucao.resize(n + 1);
    posicionarRainha(1);
    cout << totalSolucoes << endl;
    return 0;
}