Este artigo explora o problema de encontrar o maier sumbatriz retangular dentro de uma matriz dada, com a restrição de que o submatriz não pode conter nenhum ponto de obstáculo especificado.

Definições Fundamentais

Submatriz Válida

Uma submatriz válida é um retângulo cujas bordas são paralelas aos eixos de coordenadas e que não contém quaisquer obstáculos em seu interior.

Submatriz Válida Maximal

Um submatriz válida é considerada maximal se não existir nenhuma outra submatriz válida que a contenha e seja maior que ela.

Submatriz Válida de Maior Área

Dentre todas as submatrizes válidas, a de maior área (ou uma das de maior área, caso haja empates) é a submatriz de maior área.

Abordagem da Linha Flutuante (悬线法)

A técnica da "linha flutuante" envolve o uso de uma linha que se move de um lado para o outro através da matriz para determinar a maior submatriz possível.

Estrutura Geral do Algoritmo

A lógica geral para a abordagem da linha flutuannte pode ser delineada da seguinte forma:

// Inicialização das estruturas de dados
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        // l[i][j]: limite esquerdo permitindo expansão para a esquerda
        // r[i][j]: limite direito permitindo expansão para a direita
        // u[i][j]: altura máxima do submatriz válido terminando em (i, j)
        l[i][j] = r[i][j] = j;
        u[i][j] = 1;
    }
}

// Calcular limites esquerdos
for (int i = 1; i <= n; ++i) {
    for (int j = 2; j <= m; ++j) {
        if (condicao_valida(i, j, i, j - 1)) { // Verifica se pode estender para a esquerda
            l[i][j] = l[i][j - 1];
        }
    }
}

// Calcular limites direitos
for (int i = 1; i <= n; ++i) {
    for (int j = m - 1; j >= 1; --j) {
        if (condicao_valida(i, j, i, j + 1)) { // Verifica se pode estender para a direita
            r[i][j] = r[i][j + 1];
        }
    }
}

// Calcular a área máxima
int area_maxima = 0;
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        if (i > 1) {
            // Propagar informações da linha anterior se a condição for válida
            if (condicao_valida(i, j, i - 1, j)) {
                l[i][j] = std::max(l[i][j], l[i - 1][j]);
                r[i][j] = std::min(r[i][j], r[i - 1][j]);
                u[i][j] = u[i - 1][j] + 1;
            }
        }
        // Largura potencial do submatriz com base nos limites
        int largura_potencial = r[i][j] - l[i][j] + 1;
        // Altura potencial do submatriz
        int altura_potencial = u[i][j];
        // A dimensão mínima entre largura e altura limita o submatriz quadrado
        int dim_min = std::min(largura_potencial, altura_potencial);
        // Atualiza a área máxima considerando submatrizes retangulares
        area_maxima = std::max(area_maxima, largura_potencial * u[i][j]);
    }
}

Exemplo de Aplicação

Problema 1: Palácio de Jade Lunar (P4147)

Este problema pode ser resolvido diretamente aplicando a estrutura do algoritmo da linha flutuante. A condição para estender um submatriz é que os elementos adjacentes sejam iguais e representem uma área livre (por exemplo, 'F').

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

const int MAXN = 1000 + 50;
char grid[MAXN][MAXN];
int left_bound[MAXN][MAXN], right_bound[MAXN][MAXN], up_height[MAXN][MAXN];
int N, M, max_area;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> N >> M;

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            std::cin >> grid[i][j];
            left_bound[i][j] = right_bound[i][j] = j;
            up_height[i][j] = 1;
        }
    }

    // Calcular limites esquerdos
    for (int i = 1; i <= N; ++i) {
        for (int j = 2; j <= M; ++j) {
            if (grid[i][j] == 'F' && grid[i][j - 1] == 'F') {
                left_bound[i][j] = left_bound[i][j - 1];
            }
        }
    }

    // Calcular limites direitos
    for (int i = 1; i <= N; ++i) {
        for (int j = M - 1; j >= 1; --j) {
            if (grid[i][j] == 'F' && grid[i][j + 1] == 'F') {
                right_bound[i][j] = right_bound[i][j + 1];
            }
        }
    }

    // Calcular a área máxima
    max_area = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (grid[i][j] == 'F') {
                if (i > 1 && grid[i - 1][j] == 'F') {
                    up_height[i][j] = up_height[i - 1][j] + 1;
                    left_bound[i][j] = std::max(left_bound[i][j], left_bound[i - 1][j]);
                    right_bound[i][j] = std::min(right_bound[i][j], right_bound[i - 1][j]);
                }
                int current_width = right_bound[i][j] - left_bound[i][j] + 1;
                max_area = std::max(max_area, current_width * up_height[i][j]);
            }
        }
    }

    std::cout << max_area * 3 << std::endl; // O problema original pode ter uma escala específica

    return 0;
}
</algorithm></vector></iostream>

Problema 2: Estábulo de Vacas (P1578)

Para este problema, com dimensões de até 3e4, um array bidimensional explícito não é viável. Uma abordagem alternativa é iterar sobre cada obstáculo e calcular a área máxima em expansão a partir dele. A ordenação dos obstáculos é crucial.

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

struct Obstacle {
    int r, c;
};

bool compareByRow(const Obstacle& a, const Obstacle& b) {
    return a.r < b.r;
}

bool compareByCol(const Obstacle& a, const Obstacle& b) {
    return a.c < b.c;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int max_rows, max_cols, num_obstacles;
    std::cin >> max_rows >> max_cols >> num_obstacles;

    std::vector<obstacle> obstacles(num_obstacles);
    for (int i = 0; i < num_obstacles; ++i) {
        std::cin >> obstacles[i].r >> obstacles[i].c;
    }

    // Adicionar obstáculos de fronteira para simplificar os cálculos
    obstacles.push_back({0, 0});
    obstacles.push_back({0, max_cols});
    obstacles.push_back({max_rows, 0});
    obstacles.push_back({max_rows, max_cols});
    num_obstacles = obstacles.size();

    int max_rect_area = 0;

    // Expansão horizontal
    std::sort(obstacles.begin(), obstacles.end(), compareByRow);
    for (int i = 0; i < num_obstacles; ++i) {
        int upper_bound = 0;
        int lower_bound = max_cols;
        for (int j = i + 1; j < num_obstacles; ++j) {
            max_rect_area = std::max(max_rect_area, (lower_bound - upper_bound) * (obstacles[j].r - obstacles[i].r));
            if (obstacles[j].c >= obstacles[i].c) {
                lower_bound = std::min(lower_bound, obstacles[j].c);
            } else {
                upper_bound = std::max(upper_bound, obstacles[j].c);
            }
        }
    }

    // Expansão vertical
    std::sort(obstacles.begin(), obstacles.end(), compareByCol);
    for (int i = 0; i < num_obstacles; ++i) {
        int left_bound = 0;
        int right_bound = max_rows;
        for (int j = i + 1; j < num_obstacles; ++j) {
            max_rect_area = std::max(max_rect_area, (right_bound - left_bound) * (obstacles[j].c - obstacles[i].c));
            if (obstacles[j].r >= obstacles[i].r) {
                right_bound = std::min(right_bound, obstacles[j].r);
            } else {
                left_bound = std::max(left_bound, obstacles[j].r);
            }
        }
    }

    std::cout << max_rect_area << std::endl;

    return 0;
}
</obstacle></algorithm></vector></iostream>