El prbolema consiste en una matriz cuadrada de tamaño n x n (1 ≤ n ≤ 30) compuesta por valores 0 y 1, donde los 1 forman una forma cerrada. El objetivo es cambiar todos los 0 dentro de esa forma cerrada a 2. Un 0 se considera interior si, al desplazarse solo en las cuatro direcciones (arriba, abajo, izquierda, derecha) a través de otros 0, no se puede alcanzar el borde de la matriz.

Método 1: Búsqueda en apmlitud (BFS)

Este método localiza un punto interior dentro del círculo y aplica BFS para colorear todos los 0 conectados. Para encontrar un punto interior, se verifica que en las cuatro direcciones exista al menos un 1 antes de llegar al borde. Luego, desde ese punto, se expande BFS marcando los 0 como 2.

Método 2: Búsqueda en profundidad (DFS)

Este enfoque utiliza una copia de la matriz para colorear externamente los 0 accesibles desde el borde. Se aplica DFS desde una posición fuera de la matriz (como (0,0)) para marcar todos los 0 externos con 1. Los 0 restantes en la matriz original son los interiores y se cambian a 2.

Formato de entrada

La primera línea contiene un entero n. Las siguientes n líneas contienen n números (0 o 1) separados por espacios, representando la matriz.

Formato de salida

Una matriz de n x n con los 0 interiores reemplazados por 2.

Ejemplo

Entrada:
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

Salida:
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

Implementación en C++

Versión con BFS

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

int main() {
    int dimension;
    cin >> dimension;
    vector<vector<int>> grid(dimension, vector<int>(dimension));
    for (int row = 0; row < dimension; row++) {
        for (int col = 0; col < dimension; col++) {
            cin >> grid[row][col];
        }
    }

    // Localizar un punto interior verificando barreras en las cuatro direcciones
    int startRow = -1, startCol = -1;
    for (int i = 1; i < dimension - 1; i++) {
        for (int j = 1; j < dimension - 1; j++) {
            if (grid[i][j] == 0) {
                bool up = false, down = false, left = false, right = false;
                for (int k = i - 1; k >= 0; k--) if (grid[k][j] == 1) { up = true; break; }
                for (int k = i + 1; k < dimension; k++) if (grid[k][j] == 1) { down = true; break; }
                for (int k = j - 1; k >= 0; k--) if (grid[i][k] == 1) { left = true; break; }
                for (int k = j + 1; k < dimension; k++) if (grid[i][k] == 1) { right = true; break; }
                if (up && down && left && right) {
                    startRow = i;
                    startCol = j;
                    break;
                }
            }
        }
        if (startRow != -1) break;
    }

    // BFS para colorear el interior
    if (startRow != -1) {
        queue<pair<int, int>> bfsQueue;
        bfsQueue.push({startRow, startCol});
        vector<vector<bool>> visited(dimension, vector<bool>(dimension, false));
        visited[startRow][startCol] = true;
        int directionsX[] = {-1, 1, 0, 0};
        int directionsY[] = {0, 0, -1, 1};

        while (!bfsQueue.empty()) {
            auto [currentX, currentY] = bfsQueue.front();
            bfsQueue.pop();
            grid[currentX][currentY] = 2;
            for (int d = 0; d < 4; d++) {
                int nextX = currentX + directionsX[d];
                int nextY = currentY + directionsY[d];
                if (nextX >= 0 && nextX < dimension && nextY >= 0 && nextY < dimension && 
                    grid[nextX][nextY] == 0 && !visited[nextX][nextY]) {
                    visited[nextX][nextY] = true;
                    bfsQueue.push({nextX, nextY});
                }
            }
        }
    }

    // Salida de la matriz coloreada
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j < dimension; j++) {
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

Versión con DFS

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

void colorearExterno(vector<vector<int>>& canvas, int x, int y, int limit) {
    if (x < 0 || x > limit + 1 || y < 0 || y > limit + 1 || canvas[x][y] != 0) return;
    canvas[x][y] = 1;
    colorearExterno(canvas, x - 1, y, limit);
    colorearExterno(canvas, x + 1, y, limit);
    colorearExterno(canvas, x, y - 1, limit);
    colorearExterno(canvas, x, y + 1, limit);
}

int main() {
    int size;
    cin >> size;
    vector<vector<int>> originalMatrix(size, vector<int>(size));
    vector<vector<int>> canvas(size + 2, vector<int>(size + 2, 0));

    // Copiar la matriz original al lienzo con bordes expandidos
    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            cin >> originalMatrix[i - 1][j - 1];
            canvas[i][j] = originalMatrix[i - 1][j - 1];
        }
    }

    // Colorear el exterior desde la esquina (0,0)
    colorearExterno(canvas, 0, 0, size);

    // Generar salida: los 0 restantes en el lienzo son interiores, se cambian a 2
    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            if (canvas[i][j] == 0) {
                cout << 2 << " ";
            } else {
                cout << originalMatrix[i - 1][j - 1] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}