Replace Matrix - C++ Solution

1. Introduction

This blog post discusses an interesting problem of modifying a binary matrix. The objective is to replace all occurrences of 0's by 1's, which are not completely surrounded by 1's from all eight directions - top, left, bottom, right, and the four diagonals.

Problem

Given an M × N binary matrix, the task is to replace all 0’s that are not completely surrounded by 1’s with 1’s. This involves checking each cell’s eight neighbors and deciding whether to replace it.

2. Solution Steps

1. First, copy the original matrix to keep track of the original state.

2. Iterate over each element of the matrix.

3. For each 0, check its eight neighbors in the original matrix.

4. If any neighbor is 0, replace the current element with 1 in the new matrix.

5. Continue until all elements are processed.

6. The modified matrix is the final output.

3. Code Program

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

// Function to check if the cell is surrounded by 1's
bool isSurrounded(const vector<vector<int>>& matrix, int x, int y) {
    for (int i = x - 1; i <= x + 1; i++) {
        for (int j = y - 1; j <= y + 1; j++) {
            if (i >= 0 && i < matrix.size() && j >= 0 && j < matrix[0].size()) {
                if (matrix[i][j] == 0) {
                    return false;
                }
            }
        }
    }
    return true;
}

// Function to replace matrix elements
void replaceMatrix(vector<vector<int>>& matrix) {
    vector<vector<int>> original = matrix;

    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[0].size(); j++) {
            if (matrix[i][j] == 0 && !isSurrounded(original, i, j)) {
                matrix[i][j] = 1;
            }
        }
    }
}

int main() {
    vector<vector<int>> matrix = {
        {1, 1, 1, 1, 0, 0, 1, 1, 0, 1},
        // ... (other rows)
    };

    replaceMatrix(matrix);

    // Output the modified matrix
    for (const auto& row : matrix) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}

Output:

1 1 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1
1 1 1 1 0 0 1 1 1 1
1 1 1 1 0 0 0 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 0 1 0 1
1 1 1 1 1 0 1 0 0 1
1 1 1 1 1 1 1 1 1 1

Explanation:

The function replaceMatrix first creates a copy of the original matrix. It then iterates over each cell, checking if a 0 cell is surrounded by 1's using the isSurrounded function. If not, it replaces the 0 with 1. This process ensures that only those 0’s that are not completely surrounded by 1’s are replaced, as demonstrated by the given example matrix.