A busca em profundidade (DFS) é uma técnica essencial para explorar estruturas de grafos ou grades. Aplicando-a ao problema do castelo POJ1164, podemos identificar salas e calcular suas áreas de forma eficiente.

O castelo é representado por uma grade de m linhas e n colunas (com m, n ≤ 50), onde cada célula contém um número de 0 a 15. Esse número codifica as paredes presentes ao redor da célula: bit 1 (valor 1) para a parede oeste, bit 2 (valor 2) para a parede norte, bit 3 (valor 4) para a parede leste e bit 4 (valor 8) para a parede sul. As paredes internas são compartilhadas entre células adjacentes.

O objetivo é determinar:

1. O número total de salas no castelo.
2. A área da maior sala (contada em número de células).

Para visualizar, veja o exemplo de mapa abaixo:

     1   2   3   4   5   6   7  
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #
   #---#########---#####---#---#
 4 #   #   |   |   |   |   #   #
   #############################

Neste mapa, # representa uma parede, enquanto | e - indicam ausência de paredes vertical e horizontal, respectivamente.

Abordagem com Busca em Profundidade

A ideia central é percorrer cada célula da grade. Ao encontrar uma célula não visitada, realizamos uma DFS a partir dela, visitando todas as células conectadas sem paredes intermediárias. Cada DFS completa marca uma sala distinta. Durante a DFS, mantemos um contador para o tamanho da sala atual e atualizamos o tamanho máximo encontrado.

A DFS pode ser implementada de forma recursiva ou iterativa usando uma pilha para simular a recursão. A verificação de movimentos possíveis baseia-se nos bits do número da célula: se o bit correspondente a uma direção estiver zerado, há uma passagem para a célula vizinha naquela direção.

Implementação Recursiva

A seguir, uma solução em C++ que utiliza DFS recursivo. As variáveis são renomeadas para maior clareza:

#include <iostream>

using namespace std;

int linhas, colunas, contadorSalas = 0, areaMaxima = 0, areaAtual;
int grade[50][50], cor[50][50] = {0};

void dfs(int linha, int coluna) {
    cor[linha][coluna] = contadorSalas;
    areaAtual++;
    // Verifica movimentos em cada direção usando bits
    if (((grade[linha][coluna] & 1) == 0) && (coluna > 0) && !cor[linha][coluna-1])
        dfs(linha, coluna-1);
    if (((grade[linha][coluna] & 2) == 0) && (linha > 0) && !cor[linha-1][coluna])
        dfs(linha-1, coluna);
    if (((grade[linha][coluna] & 4) == 0) && (coluna+1 < colunas) && !cor[linha][coluna+1])
        dfs(linha, coluna+1);
    if (((grade[linha][coluna] & 8) == 0) && (linha+1 < linhas) && !cor[linha+1][coluna])
        dfs(linha+1, coluna);
}

int main() {
    cin >> linhas >> colunas;
    for (int i = 0; i < linhas; i++)
        for (int j = 0; j < colunas; j++)
            cin >> grade[i][j];
    for (int i = 0; i < linhas; i++)
        for (int j = 0; j < colunas; j++) {
            if (!cor[i][j]) {
                contadorSalas++;
                areaAtual = 0;
                dfs(i, j);
                if (areaAtual > areaMaxima)
                    areaMaxima = areaAtual;
            }
        }
    cout << contadorSalas << endl << areaMaxima;
    return 0;
}

Implementação com Pilha (Simulação de Recursão)

Para evitar o estouro de pilha em casos de grade grande, podemos simular a DFS iterativamente usando uma pilha. A lógica permanece semelhante, mas os estados são gerenciados explicitamente:

#include <iostream>
#include <stack>

using namespace std;

int linhas, colunas, contadorSalas = 0, areaAtual;
int grade[50][50], cor[50][50] = {0};

struct Celula {
    int linha, coluna;
    Celula(int l, int c) : linha(l), coluna(c) {}
};

void dfsIterativo(int inicioLinha, int inicioColuna) {
    stack<Celula> pilha;
    pilha.push(Celula(inicioLinha, inicioColuna));
    while (!pilha.empty()) {
        Celula atual = pilha.top();
        int linha = atual.linha;
        int coluna = atual.coluna;
        if (cor[linha][coluna]) {
            pilha.pop();
        } else {
            cor[linha][coluna] = contadorSalas;
            areaAtual++;
            // Verifica vizinhos em cada direção
            if (((grade[linha][coluna] & 1) == 0) && (coluna > 0) && !cor[linha][coluna-1])
                pilha.push(Celula(linha, coluna-1));
            if (((grade[linha][coluna] & 2) == 0) && (linha > 0) && !cor[linha-1][coluna])
                pilha.push(Celula(linha-1, coluna));
            if (((grade[linha][coluna] & 4) == 0) && (coluna+1 < colunas) && !cor[linha][coluna+1])
                pilha.push(Celula(linha, coluna+1));
            if (((grade[linha][coluna] & 8) == 0) && (linha+1 < linhas) && !cor[linha+1][coluna])
                pilha.push(Celula(linha+1, coluna));
        }
    }
}

int main() {
    int areaMaxima = 0;
    cin >> linhas >> colunas;
    for (int i = 0; i < linhas; i++)
        for (int j = 0; j < colunas; j++)
            cin >> grade[i][j];
    for (int i = 0; i < linhas; i++)
        for (int j = 0; j < colunas; j++) {
            if (!cor[i][j]) {
                contadorSalas++;
                areaAtual = 0;
                dfsIterativo(i, j);
                if (areaAtual > areaMaxima)
                    areaMaxima = areaAtual;
            }
        }
    cout << contadorSalas << endl << areaMaxima;
    return 0;
}