Problem Description

Given an n×n matrix composed of 0s and 1s, where 1s form a closed boundary, the task is to identify and fill all 0s enclosed within this boundary with 2s. A 0 is considered enclosed if it cannot reach the matrix boundary by moving only through adjacent 0s (up, down, left, right).

Input Format

• First line: integer n (1 ≤ n ≤ 30), the size of the matrix.
• Next n lines: n space-separated integers (0 or 1) representign the matrix.

Output Format

Modified matrix where enclosed 0s are replaced with 2s.

Example

Input:

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

Output:

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

Solution Approaches

1. BFS (Breadth-First Search):

   • Start from the matrix boundaries and mark all reachable 0s.
   • Unmarked 0s are enclosed and should be filled with 2s.

2. DFS (Depth-First Search):

   • Similarly, traverse from boundaries to mark accessible 0s.
   • Fill unvisited 0s with 2s.

Code Implementation

BFS Solution:

#include <bits/stdc++.h>
using namespace std;

const int N = 35;
int matrix[N][N];
int visited[N][N];
int n;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();
        if (matrix[cx][cy] == 1) continue;
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (nx >= 0 && ny >= 0 && nx < n && ny < n && matrix[nx][ny] == 0 && !visited[nx][ny]) {
                matrix[nx][ny] = -1;
                visited[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i][0] && matrix[i][0] == 0) bfs(i, 0);
        if (!visited[i][n-1] && matrix[i][n-1] == 0) bfs(i, n-1);
    }
    for (int j = 0; j < n; j++) {
        if (!visited[0][j] && matrix[0][j] == 0) bfs(0, j);
        if (!visited[n-1][j] && matrix[n-1][j] == 0) bfs(n-1, j);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == -1) cout << "0 ";
            else if (matrix[i][j] == 0) cout << "2 ";
            else cout << "1 ";
        }
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

DFS Solution:

#include <bits/stdc++.h>
using namespace std;

int n;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void dfs(int x, int y, vector<vector<int>>& grid) {
    if (x < 0 || y < 0 || x >= n || y >= n || grid[x][y] != 0) return;
    grid[x][y] = -1;
    for (int i = 0; i < 4; i++) {
        dfs(x + dx[i], y + dy[i], grid);
    }
}

void solve() {
    cin >> n;
    vector<vector<int>> grid(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        if (grid[i][0] == 0) dfs(i, 0, grid);
        if (grid[i][n-1] == 0) dfs(i, n-1, grid);
    }
    for (int j = 0; j < n; j++) {
        if (grid[0][j] == 0) dfs(0, j, grid);
        if (grid[n-1][j] == 0) dfs(n-1, j, grid);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == -1) cout << "0 ";
            else if (grid[i][j] == 0) cout << "2 ";
            else cout << "1 ";
        }
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}