Implementação de Busca em Largura (BFS) no Problema do Elevador

O problema do elevador consiste em encontrar o número mínimo de movimentos para sair de um andar A e chegar a um andar B. Cada andar possui um valor K[i], que indica que, a partir daquele andar, você só pode subir ou descer exatamente K[i] níveis, desde que o destino esteja dentro dos limites do prédio.

Como o objetivo é encontrar o caminho mais curto em um grafo onde cada aresta tem peso unitário (cada clique no botão conta como 1), a Busca em Largura (BFS) é a abordagem ideal. Utilizamos uma fila para explorar os estados e um array para rastrear a distância (número de cliques) de cada andar visitado.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/**
 * Resolve o problema do elevador utilizando BFS para encontrar o menor caminho.
 * @param n_andares Total de andares no prédio.
 * @param origem Andar inicial.
 * @param destino Andar alvo.
 */
int calcular_minimo_cliques(int n_andares, int origem, int destino) {
    if (origem == destino) return 0;

    vector<int> saltos(n_andares + 1);
    for (int i = 1; i <= n_andares; ++i) {
        cin >> saltos[i];
    }

    vector<int> passos(n_andares + 1, -1);
    queue<int> fila;

    fila.push(origem);
    passos[origem] = 0;

    while (!fila.empty()) {
        int atual = fila.front();
        fila.pop();

        if (atual == destino) return passos[destino];

        // Opções de movimento: subir ou descer
        int movimentos[] = { atual + saltos[atual], atual - saltos[atual] };

        for (int proximo : movimentos) {
            if (proximo >= 1 && proximo <= n_andares && passos[proximo] == -1) {
                passos[proximo] = passos[atual] + 1;
                fila.push(proximo);
            }
        }
    }

    return -1;
}

int main() {
    int N, A, B;
    while (cin >> N && N != 0) {
        cin >> A >> B;
        cout << calcular_minimo_cliques(N, A, B) << endl;
    }
    return 0;
}

Soma Máxima de Sub-retângulo: Somas de Prefixo e Algoritmo de Kadane

Para encontrar o sub-retângulo com a maier soma em uma matriz bidimensional, podemos reduzir a complexidade do problema transformando-o em múltiplas instâncias de um problema unidimensional. A ideia central é fixar o intervalo de linhas (superior e inferior) e compactar as colunas nesse intervalo.

O processo envolve os seguintes passos:

1. Soma de Prefixo Vertical: Pré-calculamos as somas das colunas para permitir obter a soma de qualquer segmento vertical em tempo constante O(1).
2. Compressão de Linhas: Iteramos sobre todas as combinações possíveis de linha de início (topo) e linha de fim (base).
3. Algoritmo de Kadane: Para cada par de linhas, calculamos a soma acumulada de cada coluna e aplicamos o Algoritmo de Kadane para encontrar o maior sub-array em uma dimensão.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Calcula a soma máxima de um sub-retângulo em uma matriz N x N.
 */
void resolver_soma_maxima_matriz() {
    int dim;
    if (!(cin >> dim)) return;

    vector<vector<int>> matriz(dim + 1, vector<int>(dim + 1));
    vector<vector<int>> prefixo_v(dim + 1, vector<int>(dim + 1, 0));

    for (int i = 1; i <= dim; ++i) {
        for (int j = 1; j <= dim; ++j) {
            cin >> matriz[i][j];
            // Construção da soma de prefixo por coluna
            prefixo_v[i][j] = prefixo_v[i - 1][j] + matriz[i][j];
        }
    }

    long long resultado_global = -2e18; // Valor inicial muito baixo

    // Itera sobre todas as combinações de limites horizontais (linhas)
    for (int linha_inicio = 1; linha_inicio <= dim; ++linha_inicio) {
        for (int linha_fim = linha_inicio; linha_fim <= dim; ++linha_fim) {
            
            long long soma_atual_kadane = 0;
            
            // Aplica Kadane sobre a projeção unidimensional das colunas
            for (int col = 1; col <= dim; ++col) {
                int soma_segmento_coluna = prefixo_v[linha_fim][col] - prefixo_v[linha_inicio - 1][col];
                
                // Decisão do Kadane: continuar a sequência ou iniciar uma nova do ponto atual
                soma_atual_kadane = max((long long)soma_segmento_coluna, soma_atual_kadane + soma_segmento_coluna);
                resultado_global = max(resultado_global, soma_atual_kadane);
            }
        }
    }

    cout << resultado_global << endl;
}

int main() {
    resolver_soma_maxima_matriz();
    return 0;
}

O Algoritmo de Kadane utilizado na parte interna é uma técnica de programação dinâmica que resolve o problema do "Sub-array Contíguo de Soma Máxima". Ao verificar se soma_atual + valor_novo é menor que valor_novo, o algoritmo identifica se o histórico acumulado tornou-se um "fardo" negativo, decidindo resetar a contagem se necessário.