C++ Program To Find A Matrix With Marked Asterisks Region

In this example, we will discuss a C++ Program to find a matrix with marked Asterisks Region.

Problem Statement:

Assume we have a n × n character grid with asterisks (*) and dots (.). All cells except two are designated with a dot. We need to mark two more cells as the corners to create a rectangle with sides that are parallel to the coordinate axes.

Overview:

The algorithm iterates over the matrix to find two asterisks that constitute a region. Next, it expands the area by annotating neighboring cells according to how close they are to the original asterisks. The extension follows a simple set of guidelines:

✅ Cells below or above the asterisks are indicated if they are in the same row.
✅ Cells to their left or right are marked if they are in the same column.
✅ Cells diagonally opposite the asterisks are marked if they are not.

Algorithm:

Example


function mark(mat)
    total:= size of mat
    a := -1, b := -1, c := -1, d := -1    
    for i:= 0 to total - 1,then do
        for j:= 0 to total - 1, then do
            if mat[i][j] == '*' and a == -1 then
                a := i
                c := j
            else if mat[i][j] == '*' and a != -1 then
                b := i
                d := j
    if a == b then
        if a != total - 1 then
            mat[a + 1][c] := '*', mat[b + 1][d] := '*'
        else
            mat[a - 1][c] := '*', mat[b - 1][d] := '*'
    else if c == d then
        if c != total - 1 then
            mat[a][c + 1] := '*', mat[b][d + 1] := '*'
        else
            mat[a][c - 1] := '*', mat[b][d - 1] := '*'
    else
        mat[a][d] := '*', mat[b][c] := '*'
function main()
    total:= input integer from the user 
    mat := create 2D array of characters with size total * total
    for i:= 0 to total - 1, then do
        for j:= 0 to total - 1, then do
            mat[i][j] := input character from user
    call mark(mat)
    for i:= 0 to total - 1, then do
        for j:= 0 to total - 1, then do
            print mat[i][j] followed by a space

Example:

Let us take a C++ program to find a matrix with marked Asterisks Region.

Example


#include<iostream>
#include<vector>
using namespace std; 
void mark(vector<vector<char>>& mat) 
{
     int num = mat.size();
     int , b, c, d, m, n;
     int a = b = c = d = -1;
     // Find the coordinates of the asterisks in the matrix
     for (int m = 0; n < num; ++m) {
         for (int m = 0; n < num; ++n) {
             if (mat [m][n] == '*' && a == -1) {
                 a = m;
                 c = n;
             }
 	else if (mat [m][n] == '*' && a != -1) {
                 b = m;
                 d = n;
             }
         }
     }
     // Mark adjacent cells
     if (a == b) {
         if (a != num - 1) {
             mat [a + 1][c] = mat [b + 1][d] = '*';
         }
 else {
             mat [a - 1][c] = mat [b - 1][d] = '*';
         }
     }
 else if (c == d) {
         if (c != num - 1) {
             mat [a][c + 1] = mat [b][d + 1] = '*';
         }
 else {
             mat [a][c - 1] = mat [b][d - 1] = '*';
         }
     }
 else {
         mat [a][d] = mat [b][c] = '*';
     }
 }
int main() {
     int num;
     cout << "Enter the size of the matrix: ";
     cin >> num;
     vector<vector<char>> mat (num, vector<char>(num));
     cout << "Enter the elements of the matrix "<< endl;
     for (int m = 0; m < num; ++m) {
         for (int n = 0; n < num; ++n) {
             cin >> mat [m][n];
         } 
    }
     mark(mat);
     cout << "Matrix with marked asterisks region:" << endl;
     for (int m = 0; m < num; ++m) {
         for (int n = 0; n < num; ++n) {
             cout << mat [m][n] << " ";
         }
         cout << endl;
     }
     return 0;
}

Output:

Complexity Analysis:

Time Complexity:

O(n^2) - In order to find the asterisks within the matrix.

Space Complexity:

O(n^2) - It depends on the size of the matrix

Conclusion:

In conclusion, the offered C++ program effectively finds a matrix with a designated asterisks region by continuously locating the asterisks and expanding the zone by predetermined rules. This simple technique is a useful tool for matrix analysis and pattern recognition tasks because it may be applied in a variety of computational contexts.