Manipulação de Strings com <string>

O processamento eficiente de strings é fundamental para algoritmos que envolvem padrões de texto. Em C++, a biblioteca <string> oferece uma interface robusta para essas operações:

• Concatenação: Pode ser feita via operador += ou pelo método append().
• Dimensão: Os métodos size() e length() retornam o número de caracteres.
• Substrings: texto.substr(posicao, tamanho) extrai uma sequência a partir de um índice específico.
• Busca: find("alvo") localiza a primeira ocorrência, enquanto rfind("alvo") busca de trás para frente.
• Modificação: replace(pos, len, "novo") substitui trechos; insert(pos, "texto") e erase(pos, len) gerenciam a inserção e remoção.
• Conversão de Case: Utilizando <algorithm>, é possível transformar a string: ``` std::transform(s.begin(), s.end(), s.begin(), ::tolower);

• Interoperabilidade: c_str() converte para um array de caracteres (char*), útil para funções legadas de C como printf.

Gerenciamento de Matrizes com Vetores Dinâmicos

Para lidar com grades de dimansões variáveis, a estrutura vector<vector<int>> é a escolha padrão, permitindo inicialização flexível:

// Matriz n x n inicializada com zeros
vector<vector<int>> grade(n, vector<int>(n, 0));

// Redimensionamento posterior
vector<vector<int>> matriz;
matriz.resize(linhas, vector<int>(colunas));

Abordagem 1: Força Bruta com Binarização

Nesta estratégia, para cada valor de limiar \(k\) possível, a matriz original é converitda em uma matriz de strings binárias (0 ou 1). Em seguida, verifica-se se o padrão da marca d'água existe na matriz resultante. O custo computacional é de aproximadamente \(O(L \times n^2)\).

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Converte a matriz numérica para representação de strings baseada no limiar k
vector<string> binarizar(const vector<vector<int>>& original, int k, int dim) {
    vector<string> binaria(dim, "");
    for(int i = 0; i < dim; ++i) {
        for(int j = 0; j < dim; ++j) {
            binaria[i] += (original[i][j] >= k ? '1' : '0');
        }
    }
    return binaria;
}

bool validar_padrao(const vector<string>& grade, const vector<string>& alvo, int linha_inicio) {
    int colunas = grade[0].size();
    for(int j = 0; j <= colunas - 9; ++j) {
        bool match = true;
        for(int r = 0; r < 5; ++r) {
            if(grade[linha_inicio + r].substr(j, 9) != alvo[r]) {
                match = false;
                break;
            }
        }
        if(match) return true;
    }
    return false;
}

int main() {
    int n, L;
    if(!(cin >> n >> L)) return 0;

    vector<string> marca = {
        "111111111",
        "100100101",
        "100111110",
        "100001100",
        "111111100"
    };

    vector<vector<int>> dados(n, vector<int>(n));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> dados[i][j];

    for(int k = 0; k < L; k++) {
        vector<string> camada = binarizar(dados, k, n);
        for(int i = 0; i <= n - 5; i++) {
            if(validar_padrao(camada, marca, i)) {
                cout << k << endl;
                break;
            }
        }
    }
    return 0;
}

Abordagem 2: Otimização via Restrições de Intervalo e Diferença

Em vez de testar cada \(k\), podemos analisar cada janela de \(5 \times 9\) na matriz. Para que uma janela coincida com o padrão da marca d'água sob um limiar \(k\), as seguintes condições devem ser atendidas:

• Se o padrão tem '1', então \(matriz[i][j] \ge k\).
• Se o padrão tem '0', então \(matriz[i][j] < k\).

Isso define um intervalo válido para \(k\): \(k \in [k_{min}, k_{max}]\). Usando um Array de Diferenças, podemos marcar eses intervalos de forma eficiente em \(O(n^2)\).

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

using namespace std;

int main() {
    int n, L;
    cin >> n >> L;

    int padrao[5][9] = {
        {1,1,1,1,1,1,1,1,1},
        {1,0,0,1,0,0,1,0,1},
        {1,0,0,1,1,1,1,1,0},
        {1,0,0,0,0,1,1,0,0},
        {1,1,1,1,1,1,1,0,0}
    };

    vector<vector<int>> matriz(n, vector<int>(n));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> matriz[i][j];

    vector<int> diff(L + 2, 0);

    for(int i = 0; i <= n - 5; i++) {
        for(int j = 0; j <= n - 9; j++) {
            int limite_superior = L - 1;
            int limite_inferior = 0;

            for(int r = 0; r < 5; r++) {
                for(int c = 0; c < 9; c++) {
                    if(padrao[r][c] == 1)
                        limite_superior = min(limite_superior, matriz[i+r][j+c]);
                    else
                        limite_inferior = max(limite_inferior, matriz[i+r][j+c] + 1);
                }
            }

            if(limite_inferior <= limite_superior) {
                diff[limite_inferior]++;
                diff[limite_superior + 1]--;
            }
        }
    }

    int soma_prefixa = 0;
    for(int k = 0; k < L; k++) {
        soma_prefixa += diff[k];
        if(soma_prefixa > 0) {
            cout << k << endl;
        }
    }

    return 0;
}