Check if a matrix contains a square submatrix with 0 as boundary element | C # implementation of the above approach ; Function checks if square with all 0 's in boundary  exists in the matrix ; r1 is the top row , c1 is the left col r2 is the bottom row , c2 is the right ; Function checks if the boundary of the square consists of 0 's ; Driver Code
using System ; using System . Collections . Generic ; class GFG { static int squareOfZeroes ( int [ , ] matrix ) { int lastIdx = matrix . GetLength ( 0 ) - 1 ; Dictionary < string , bool > cache = new Dictionary < string , bool > ( ) ; if ( hasSquareOfZeroes ( matrix , 0 , 0 , lastIdx , lastIdx , cache ) ) { return 1 ; } else { return 0 ; } } static bool hasSquareOfZeroes ( int [ , ] matrix , int r1 , int c1 , int r2 , int c2 , Dictionary < string , bool > cache ) { if ( r1 >= r2 c1 >= c2 ) { return false ; } string key = r1 + " - " + c1 + " - " + r2 + " - " + c2 ; if ( cache . ContainsKey ( key ) ) { return cache [ key ] ; } cache [ key ] = ( isSquareOfZeroes ( matrix , r1 , c1 , r2 , c2 ) || hasSquareOfZeroes ( matrix , r1 + 1 , c1 + 1 , r2 - 1 , c2 - 1 , cache ) || hasSquareOfZeroes ( matrix , r1 , c1 + 1 , r2 - 1 , c2 , cache ) || hasSquareOfZeroes ( matrix , r1 + 1 , c1 , r2 , c2 - 1 , cache ) || hasSquareOfZeroes ( matrix , r1 + 1 , c1 + 1 , r2 , c2 , cache ) || hasSquareOfZeroes ( matrix , r1 , c1 , r2 - 1 , c2 - 1 , cache ) ) ; return cache [ key ] ; } static bool isSquareOfZeroes ( int [ , ] matrix , int r1 , int c1 , int r2 , int c2 ) { for ( int row = r1 ; row < r2 + 1 ; row ++ ) { if ( matrix [ row , c1 ] != 0 matrix [ row , c2 ] != 0 ) { return false ; } } for ( int col = c1 ; col < c2 + 1 ; col ++ ) { if ( matrix [ r1 , col ] != 0 matrix [ r2 , col ] != 0 ) { return false ; } } return true ; } static public void Main ( ) { int [ , ] matrix = { { 1 , 1 , 1 , 0 , 1 , 0 } , { 0 , 0 , 0 , 0 , 0 , 1 } , { 0 , 1 , 1 , 1 , 0 , 1 } , { 0 , 0 , 0 , 1 , 0 , 1 } , { 0 , 1 , 1 , 1 , 0 , 1 } , { 0 , 0 , 0 , 0 , 0 , 1 } } ; int ans ; ans = squareOfZeroes ( matrix ) ; if ( ans == 1 ) { Console . WriteLine ( " True " ) ; } else { Console . WriteLine ( " False " ) ; } } }