Fill Matrix - C++ Solution

1. Introduction

This blog post explores an intriguing matrix manipulation problem - filling a binary matrix with alternating rectangles of 1's and 0's. Such patterns are not only visually interesting but also find applications in various computer graphics and design algorithms.

Problem

Given an M × N binary matrix, the challenge is to fill it with alternating rectangles of 1’s and 0’s. Each successive rectangle is filled with the alternate number from its immediate outer rectangle.

2. Solution Steps

1. Initialize a matrix of size M × N with 0’s.

2. Iterate through the matrix in layers, starting from the outermost layer and moving inwards.

3. Fill each layer with alternating 1's and 0's.

4. For each layer, alternate the filling pattern between 1's and 0's.

5. Continue this process until all layers are filled.

3. Code Program

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

vector<vector<int>> fillMatrix(int M, int N) {
    vector<vector<int>> matrix(M, vector<int>(N));
    int top = 0, bottom = M - 1, left = 0, right = N - 1;
    int value = 1; // Starting with 1

    while (top <= bottom && left <= right) {
        // Fill top row
        for (int i = left; i <= right; i++) {
            matrix[top][i] = value;
        }
        top++;

        // Fill right column
        for (int i = top; i <= bottom; i++) {
            matrix[i][right] = value;
        }
        right--;

        // Fill bottom row
        if (top <= bottom) {
            for (int i = right; i >= left; i--) {
                matrix[bottom][i] = value;
            }
            bottom--;
        }

        // Fill left column
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                matrix[i][left] = value;
            }
            left++;
        }

        // Alternate between 1 and 0
        value = 1 - value;
    }

    return matrix;
}

int main() {
    int M = 10, N = 8;
    vector<vector<int>> result = fillMatrix(M, N);

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

Output:

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

Explanation:

The function fillMatrix creates an M × N matrix and fills it with alternating rectangles of 1's and 0's. It does this by iterating over the matrix in a spiral order, starting from the outermost layer and moving inwards. In each layer, it alternates between filling with 1's and 0's. This approach results in a visually appealing pattern, as shown in the output for a 10 × 8 matrix.