Count square submatrices with all ones

Here given code implementation process.

// C Program 
// Count square submatrices with all ones

#include <stdio.h>

// Matrix size
#define R 4
#define C 6


// Returns the minimum value of given two numbers (integer)
int minimum(int a,int b)
{
	if(a > b)
	{
		return b;
	}
	else
	{
		return a;
	}

}

//count number of square submatrices with all 1s
void countSquareOnce(int matrix[R][C])
{

	// Auxiliary matrix which is used to find and store all square matrix
	int auxiliary[R][C];

	// Loop controllong variables
	int i = 0;
	int j = 0;

	int result = 0;

	// Set first element of each rows
	for (i = 0; i < R; ++i)
	{
		auxiliary[i][0] = matrix[i][0];
		result += matrix[i][0];
	}
	// Set first element of each columns
	for (j = 0; j < C; ++j)
	{
		auxiliary[0][j] = matrix[0][j];

		result += matrix[0][j];
	}

	for (i = 1; i < R; ++i)
	{

		for (j = 1; j < C; ++j)
		{

			if(matrix[i][j]==1)
			{
				/*
				Set x location value by minimum of side three elements (such as).			
				x [this is current location]

					e2   e3
					  ╲   │
					   ╲  │
					    ╲ │			
					e1‒‒‒ x
				*/
				auxiliary[i][j] =  minimum(minimum(auxiliary[i][j-1],auxiliary[i-1][j-1]), auxiliary[i-1][j])+1;
			}
			else
			{
				auxiliary[i][j] = matrix[i][j];
			}

			result += auxiliary[i][j];
		}
	}

	printf("\n Total Square submatrix of 1's is : %d \n",result);

}

int main(int argc, char const *argv[])
{
    // Define matrix of integer element which contains (0 and 1)
	int matrix[R][C] =	
	{
		{0,1,0,1,1,0},
		{0,1,1,1,1,1},
		{1,1,1,1,1,1},
		{1,0,1,1,1,1}
	}; 
	
    countSquareOnce(matrix);

    return 0;
}

Output

 Total Square submatrix of 1's is : 29
/*
  Java Program for
  Count square submatrices with all ones
*/
class SquareSubmatrix
{
    // Returns the minimum value of given two numbers (integer)
    public int minimum(int a, int b)
    {
        if (a > b)
        {
            return b;
        }
        else
        {
            return a;
        }
    }
    //count number of square submatrices with all 1s
    public void countSquareOnce(int[][] matrix)
    {
        int row = matrix.length;
        int col = matrix[0].length;
        // Auxiliary matrix which is used to find and store all square matrix
        int[][] auxiliary = new int[row][col];
        // Loop controllong variables
        int i = 0;
        int j = 0;
        int result = 0;
        // Set first element of each rows
        for (i = 0; i < row; ++i)
        {
            auxiliary[i][0] = matrix[i][0];
            result += matrix[i][0];
        }
        // Set first element of each columns
        for (j = 0; j < col; ++j)
        {
            auxiliary[0][j] = matrix[0][j];
            result += matrix[0][j];
        }
        for (i = 1; i < row; ++i)
        {
            for (j = 1; j < col; ++j)
            {
                if (matrix[i][j] == 1)
                {
                    /*
                    Set x location value by minimum of side three elements (such as).           
                    x [this is current location]

                        e2   e3
                          ╲   │
                           ╲  │
                            ╲ │         
                        e1‒‒‒ x
                    */
                    auxiliary[i][j] = minimum(minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1;
                }
                else
                {
                    auxiliary[i][j] = matrix[i][j];
                }
                result += auxiliary[i][j];
            }
        }
        System.out.print("\n Total Square submatrix of 1's is : " + result + " \n");
    }
    public static void main(String[] args)
    {
        SquareSubmatrix task = new SquareSubmatrix();
        // Define matrix of integer element which contains (0 and 1)
        int[][] matrix = 
        {
            {
                0 , 1 , 0 , 1 , 1 , 0
            }, 
            {
                0 , 1 , 1 , 1 , 1 , 1
            }, 
            {
                1 , 1 , 1 , 1 , 1 , 1
            }, 
            {
                1 , 0 , 1 , 1 , 1 , 1
            }
        };
        task.countSquareOnce(matrix);
    }
}

Output

 Total Square submatrix of 1's is : 29
// Include header file
#include <iostream>
// Matrix size
#define R 4
#define C 6

using namespace std;

/*
  C++ Program for
  Count square submatrices with all ones
*/

class SquareSubmatrix
{
    public:
        // Returns the minimum value of given two numbers (integer)
        int minimum(int a, int b)
        {
            if (a > b)
            {
                return b;
            }
            else
            {
                return a;
            }
        }
    //count number of square submatrices with all 1s
    void countSquareOnce(int matrix[R][C])
    {
      
        // Auxiliary matrix which is used to find and store all square matrix
        int auxiliary[R][C];
        // Loop controllong variables
        int i = 0;
        int j = 0;
        int result = 0;
        // Set first element of each rows
        for (i = 0; i < R; ++i)
        {
            auxiliary[i][0] = matrix[i][0];
            result += matrix[i][0];
        }
        // Set first element of each columns
        for (j = 0; j < C; ++j)
        {
            auxiliary[0][j] = matrix[0][j];
            result += matrix[0][j];
        }
        for (i = 1; i < R; ++i)
        {
            for (j = 1; j < C; ++j)
            {
                if (matrix[i][j] == 1)
                {
                    /*
                    Set x location value by minimum of side three elements (such as).           
                    x [this is current location]

                        e2   e3
                          ╲   │
                           ╲  │
                            ╲ │         
                        e1‒‒‒ x
                    */
                    auxiliary[i][j] = this->minimum(this->minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1;
                }
                else
                {
                    auxiliary[i][j] = matrix[i][j];
                }
                result += auxiliary[i][j];
            }
        }
        cout << "\n Total Square submatrix of 1's is : " << result << " \n";
    }
};
int main()
{
    SquareSubmatrix task = SquareSubmatrix();
    // Define matrix of integer element which contains (0 and 1)
    int matrix[R][C] = {
        {
            0 , 1 , 0 , 1 , 1 , 0
        } , {
            0 , 1 , 1 , 1 , 1 , 1
        } , {
            1 , 1 , 1 , 1 , 1 , 1
        } , {
            1 , 0 , 1 , 1 , 1 , 1
        }
    };
    task.countSquareOnce(matrix);
    return 0;
}

Output

 Total Square submatrix of 1's is : 29
// Include namespace system
using System;
/*
  C# Program for
  Count square submatrices with all ones
*/
public class SquareSubmatrix
{
	// Returns the minimum value of given two numbers (integer)
	public int minimum(int a, int b)
	{
		if (a > b)
		{
			return b;
		}
		else
		{
			return a;
		}
	}
	//count number of square submatrices with all 1s
	public void countSquareOnce(int[,] matrix)
	{
		int row = matrix.GetLength(0);
		int col = matrix.GetLength(1);
		// Auxiliary matrix which is used to find and store all square matrix
		int[,] auxiliary = new int[row,col];
		// Loop controllong variables
		int i = 0;
		int j = 0;
		int result = 0;
		// Set first element of each rows
		for (i = 0; i < row; ++i)
		{
			auxiliary[i,0] = matrix[i,0];
			result += matrix[i,0];
		}
		// Set first element of each columns
		for (j = 0; j < col; ++j)
		{
			auxiliary[0,j] = matrix[0,j];
			result += matrix[0,j];
		}
		for (i = 1; i < row; ++i)
		{
			for (j = 1; j < col; ++j)
			{
				if (matrix[i,j] == 1)
				{
					/*
					Set x location value by minimum of side three elements (such as).			
					x [this is current location]

						e2   e3
						  ╲   │
						   ╲  │
						    ╲ │			
						e1‒‒‒ x
					*/
					auxiliary[i,j] = minimum(minimum(auxiliary[i,j - 1], auxiliary[i - 1,j - 1]), auxiliary[i - 1,j]) + 1;
				}
				else
				{
					auxiliary[i,j] = matrix[i,j];
				}
				result += auxiliary[i,j];
			}
		}
		Console.Write("\n Total Square submatrix of 1's is : " + result + " \n");
	}
	public static void Main(String[] args)
	{
		SquareSubmatrix task = new SquareSubmatrix();
		// Define matrix of integer element which contains (0 and 1)
		int[,] matrix = {
			{
				0 , 1 , 0 , 1 , 1 , 0
			} , {
				0 , 1 , 1 , 1 , 1 , 1
			} , {
				1 , 1 , 1 , 1 , 1 , 1
			} , {
				1 , 0 , 1 , 1 , 1 , 1
			}
		};
		task.countSquareOnce(matrix);
	}
}

Output

 Total Square submatrix of 1's is : 29
<?php
/*
  Php Program for
  Count square submatrices with all ones
*/
class SquareSubmatrix
{
	// Returns the minimum value of given two numbers (integer)
	public	function minimum($a, $b)
	{
		if ($a > $b)
		{
			return $b;
		}
		else
		{
			return $a;
		}
	}
	//count number of square submatrices with all 1s
	public	function countSquareOnce( & $matrix)
	{
		$row = count($matrix);
		$col = count($matrix[0]);
		// Auxiliary matrix which is used to find and store all square matrix
		$auxiliary = array_fill(0, $row, array_fill(0, $col, 0));
		// Loop controllong variables
		$i = 0;
		$j = 0;
		$result = 0;
		// Set first element of each rows
		for ($i = 0; $i < $row; ++$i)
		{
			$auxiliary[$i][0] = $matrix[$i][0];
			$result += $matrix[$i][0];
		}
		// Set first element of each columns
		for ($j = 0; $j < $col; ++$j)
		{
			$auxiliary[0][$j] = $matrix[0][$j];
			$result += $matrix[0][$j];
		}
		for ($i = 1; $i < $row; ++$i)
		{
			for ($j = 1; $j < $col; ++$j)
			{
				if ($matrix[$i][$j] == 1)
				{
					/*
					Set x location value by minimum of side three elements (such as).			
					x [this is current location]

						e2   e3
						  ╲   │
						   ╲  │
						    ╲ │			
						e1‒‒‒ x
					*/
					$auxiliary[$i][$j] = $this->minimum($this->minimum($auxiliary[$i][$j - 1], $auxiliary[$i - 1][$j - 1]), $auxiliary[$i - 1][$j]) + 1;
				}
				else
				{
					$auxiliary[$i][$j] = $matrix[$i][$j];
				}
				$result += $auxiliary[$i][$j];
			}
		}
		echo "\n Total Square submatrix of 1's is : ". $result ." \n";
	}
}

function main()
{
	$task = new SquareSubmatrix();
	// Define matrix of integer element which contains (0 and 1)
	$matrix = array(
      array(0, 1, 0, 1, 1, 0), 
      array(0, 1, 1, 1, 1, 1),
      array(1, 1, 1, 1, 1, 1), 
      array(1, 0, 1, 1, 1, 1)
    );
	$task->countSquareOnce($matrix);
}
main();

Output

 Total Square submatrix of 1's is : 29
/*
  Node Js Program for
  Count square submatrices with all ones
*/
class SquareSubmatrix
{
	// Returns the minimum value of given two numbers (integer)
	minimum(a, b)
	{
		if (a > b)
		{
			return b;
		}
		else
		{
			return a;
		}
	}
	//count number of square submatrices with all 1s
	countSquareOnce(matrix)
	{
		var row = matrix.length;
		var col = matrix[0].length;
		// Auxiliary matrix which is used to find and store all square matrix
		var auxiliary = Array(row).fill(0).map(() => new Array(col).fill(0));
		// Loop controllong variables
		var i = 0;
		var j = 0;
		var result = 0;
		// Set first element of each rows
		for (i = 0; i < row; ++i)
		{
			auxiliary[i][0] = matrix[i][0];
			result += matrix[i][0];
		}
		// Set first element of each columns
		for (j = 0; j < col; ++j)
		{
			auxiliary[0][j] = matrix[0][j];
			result += matrix[0][j];
		}
		for (i = 1; i < row; ++i)
		{
			for (j = 1; j < col; ++j)
			{
				if (matrix[i][j] == 1)
				{
					/*
					Set x location value by minimum of side three elements (such as).			
					x [this is current location]

						e2   e3
						  ╲   │
						   ╲  │
						    ╲ │			
						e1‒‒‒ x
					*/
					auxiliary[i][j] = this.minimum(this.minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1;
				}
				else
				{
					auxiliary[i][j] = matrix[i][j];
				}
				result += auxiliary[i][j];
			}
		}
		process.stdout.write("\n Total Square submatrix of 1's is : " + result + " \n");
	}
}

function main()
{
	var task = new SquareSubmatrix();
	// Define matrix of integer element which contains (0 and 1)
	var matrix = [
		[0, 1, 0, 1, 1, 0] , 
        [0, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1] , 
        [1, 0, 1, 1, 1, 1]
	];
	task.countSquareOnce(matrix);
}
main();

Output

 Total Square submatrix of 1's is : 29
#   Python 3 Program for
#   Count square submatrices with all ones

class SquareSubmatrix :
	#  Returns the minimum value of given two numbers (integer)
	def minimum(self, a, b) :
		if (a > b) :
			return b
		else :
			return a
		
	
	# count number of square submatrices with all 1s
	def countSquareOnce(self, matrix) :
		row = len(matrix)
		col = len(matrix[0])
		#  Auxiliary matrix which is used to find and store all square matrix
		auxiliary = [[0] * (col) for _ in range(row) ]
		#  Loop controllong variables
		i = 0
		j = 0
		result = 0
		#  Set first element of each rows
		while (i < row) :
			auxiliary[i][0] = matrix[i][0]
			result += matrix[i][0]
			i += 1
		
		#  Set first element of each columns
		while (j < col) :
			auxiliary[0][j] = matrix[0][j]
			result += matrix[0][j]
			j += 1
		
		i = 1
		while (i < row) :
			j = 1
			while (j < col) :
				if (matrix[i][j] == 1) :
					# 
					# Set x location value by minimum of side three elements (such as).	
					# x [this is current location]
					# 	e2   e3
					# 	  ╲   │
					# 	   ╲  │
					# 	    ╲ │			
					# 	e1‒‒‒ x
					
					auxiliary[i][j] = self.minimum(self.minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1
				else :
					auxiliary[i][j] = matrix[i][j]
				
				result += auxiliary[i][j]
				j += 1
			
			i += 1
		
		print("\n Total Square submatrix of 1's is : ", result ," ")
	

def main() :
	task = SquareSubmatrix()
	#  Define matrix of integer element which contains (0 and 1)
	matrix = [
		[0, 1, 0, 1, 1, 0] , 
        [0, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1] , 
        [1, 0, 1, 1, 1, 1]
	]
	task.countSquareOnce(matrix)

if __name__ == "__main__": main()

Output

 Total Square submatrix of 1's is :  29
#   Ruby Program for
#   Count square submatrices with all ones

class SquareSubmatrix 
	#  Returns the minimum value of given two numbers (integer)
	def minimum(a, b) 
		if (a > b) 
			return b
		else 
			return a
		end

	end

	# count number of square submatrices with all 1s
	def countSquareOnce(matrix) 
		row = matrix.length
		col = matrix[0].length
		#  Auxiliary matrix which is used to find and store all square matrix
		auxiliary = Array.new(row) {Array.new(col) {0}}
		#  Loop controllong variables
		i = 0
		j = 0
		result = 0
		#  Set first element of each rows
		while (i < row) 
			auxiliary[i][0] = matrix[i][0]
			result += matrix[i][0]
			i += 1
		end

		#  Set first element of each columns
		while (j < col) 
			auxiliary[0][j] = matrix[0][j]
			result += matrix[0][j]
			j += 1
		end

		i = 1
		while (i < row) 
			j = 1
			while (j < col) 
				if (matrix[i][j] == 1) 
					# 
					# Set x location value by minimum of side three elements (such as).	
					# x [this is current location]
					# 	e2   e3
					# 	  ╲   │
					# 	   ╲  │
					# 	    ╲ │			
					# 	e1‒‒‒ x
					
					auxiliary[i][j] = self.minimum(self.minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1
				else 
					auxiliary[i][j] = matrix[i][j]
				end

				result += auxiliary[i][j]
				j += 1
			end

			i += 1
		end

		print("\n Total Square submatrix of 1's is : ", result ," \n")
	end

end

def main() 
	task = SquareSubmatrix.new()
	#  Define matrix of integer element which contains (0 and 1)
	matrix = [
		[0, 1, 0, 1, 1, 0] , 
        [0, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1] , 
        [1, 0, 1, 1, 1, 1]
	]
	task.countSquareOnce(matrix)
end

main()

Output

 Total Square submatrix of 1's is : 29 
/*
  Scala Program for
  Count square submatrices with all ones
*/
class SquareSubmatrix
{
	// Returns the minimum value of given two numbers (integer)
	def minimum(a: Int, b: Int): Int = {
		if (a > b)
		{
			return b;
		}
		else
		{
			return a;
		}
	}
	//count number of square submatrices with all 1s
	def countSquareOnce(matrix: Array[Array[Int]]): Unit = {
		var row: Int = matrix.length;
		var col: Int = matrix(0).length;
		// Auxiliary matrix which is used to find and store all square matrix
		var auxiliary: Array[Array[Int]] = Array.fill[Int](row, col)(0);
		// Loop controllong variables
		var i: Int = 0;
		var j: Int = 0;
		var result: Int = 0;
		// Set first element of each rows
		while (i < row)
		{
			auxiliary(i)(0) = matrix(i)(0);
			result += matrix(i)(0);
			i += 1;
		}
		// Set first element of each columns
		while (j < col)
		{
			auxiliary(0)(j) = matrix(0)(j);
			result += matrix(0)(j);
			j += 1;
		}
		i = 1;
		while (i < row)
		{
			j = 1;
			while (j < col)
			{
				if (matrix(i)(j) == 1)
				{
					/*
					Set x location value by minimum of side three elements (such as).			
					x [this is current location]

						e2   e3
						  ╲   │
						   ╲  │
						    ╲ │			
						e1‒‒‒ x
					*/
					auxiliary(i)(j) = this.minimum(this.minimum(auxiliary(i)(j - 1), auxiliary(i - 1)(j - 1)), auxiliary(i - 1)(j)) + 1;
				}
				else
				{
					auxiliary(i)(j) = matrix(i)(j);
				}
				result += auxiliary(i)(j);
				j += 1;
			}
			i += 1;
		}
		print("\n Total Square submatrix of 1's is : " + result + " \n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: SquareSubmatrix = new SquareSubmatrix();
		// Define matrix of integer element which contains (0 and 1)
		var matrix: Array[Array[Int]] = Array(
          Array(0, 1, 0, 1, 1, 0), 
          Array(0, 1, 1, 1, 1, 1), 
          Array(1, 1, 1, 1, 1, 1), 
          Array(1, 0, 1, 1, 1, 1)
        );
		task.countSquareOnce(matrix);
	}
}

Output

 Total Square submatrix of 1's is : 29
/*
  Swift 4 Program for
  Count square submatrices with all ones
*/
class SquareSubmatrix
{
	// Returns the minimum value of given two numbers (integer)
	func minimum(_ a: Int, _ b: Int)->Int
	{
		if (a > b)
		{
			return b;
		}
		else
		{
			return a;
		}
	}
	//count number of square submatrices with all 1s
	func countSquareOnce(_ matrix: [
		[Int]
	])
	{
		let row: Int = matrix.count;
		let col: Int = matrix[0].count;
		// Auxiliary matrix which is used to find and store all square matrix
		var auxiliary: [[Int]] = Array(repeating: Array(repeating: 0, count: col), count: row);
		// Loop controllong variables
		var i: Int = 0;
		var j: Int = 0;
		var result: Int = 0;
		// Set first element of each rows
		while (i < row)
		{
			auxiliary[i][0] = matrix[i][0];
			result += matrix[i][0];
			i += 1;
		}
		// Set first element of each columns
		while (j < col)
		{
			auxiliary[0][j] = matrix[0][j];
			result += matrix[0][j];
			j += 1;
		}
		i = 1;
		while (i < row)
		{
			j = 1;
			while (j < col)
			{
				if (matrix[i][j] == 1)
				{
					/*
					Set x location value by minimum of side three elements (such as).			
					x [this is current location]

						e2   e3
						  ╲   │
						   ╲  │
						    ╲ │			
						e1‒‒‒ x
					*/
					auxiliary[i][j] = self.minimum(self.minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1;
				}
				else
				{
					auxiliary[i][j] = matrix[i][j];
				}
				result += auxiliary[i][j];
				j += 1;
			}
			i += 1;
		}
		print("\n Total Square submatrix of 1's is : ", result ," ");
	}
}
func main()
{
	let task: SquareSubmatrix = SquareSubmatrix();
	// Define matrix of integer element which contains (0 and 1)
	let matrix: [[Int]] = [
		[0, 1, 0, 1, 1, 0] , 
        [0, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1] , 
        [1, 0, 1, 1, 1, 1]
	];
	task.countSquareOnce(matrix);
}
main();

Output

 Total Square submatrix of 1's is :  29
/*
  Kotlin Program for
  Count square submatrices with all ones
*/
class SquareSubmatrix
{
	// Returns the minimum value of given two numbers (integer)
	fun minimum(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return b;
		}
		else
		{
			return a;
		}
	}
	//count number of square submatrices with all 1s
	fun countSquareOnce(matrix: Array < Array < Int >> ): Unit
	{
		var row: Int = matrix.count();
		var col: Int = matrix[0].count();
		// Auxiliary matrix which count() used to find and store all square matrix
		var auxiliary: Array < Array < Int >> = Array(row)
		{
			Array(col)
			{
				0
			}
		};
		// Loop controllong variables
		var i: Int = 0;
		var j: Int = 0;
		var result: Int = 0;
		// Set first element of each rows
		while (i < row)
		{
			auxiliary[i][0] = matrix[i][0];
			result += matrix[i][0];
			i += 1;
		}
		// Set first element of each columns
		while (j < col)
		{
			auxiliary[0][j] = matrix[0][j];
			result += matrix[0][j];
			j += 1;
		}
		i = 1;
		while (i < row)
		{
			j = 1;
			while (j < col)
			{
				if (matrix[i][j] == 1)
				{
					/*
					Set x location value by minimum of side three elements (such as).			
					x [this is current location]

						e2   e3
						  ╲   │
						   ╲  │
						    ╲ │			
						e1‒‒‒ x
					*/
					auxiliary[i][j] = this.minimum(this.minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1;
				}
				else
				{
					auxiliary[i][j] = matrix[i][j];
				}
				result += auxiliary[i][j];
				j += 1;
			}
			i += 1;
		}
		print("\n Total Square submatrix of 1's is : " + result + " \n");
	}
}
fun main(args: Array < String > ): Unit
{
	var task: SquareSubmatrix = SquareSubmatrix();
	// Define matrix of integer element which contains (0 and 1)
	var matrix: Array <Array<Int>> = arrayOf(
      arrayOf(0, 1, 0, 1, 1, 0), 
      arrayOf(0, 1, 1, 1, 1, 1), 
      arrayOf(1, 1, 1, 1, 1, 1), 
      arrayOf(1, 0, 1, 1, 1, 1)
    );
	task.countSquareOnce(matrix);
}

Output

 Total Square submatrix of 1's is : 29

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved