Find sub | PHP implementation of the approach ; Function to return the sum of the sub - matrix ; Function that returns true if it is possible to find the sub - matrix with required sum ; 2 - D array to store the sum of all the sub - matrices ; Filling of dp [ ] [ ] array ; Checking for each possible sub - matrix of size k X k ; Sub - matrix with the given sum not found ; Driver code ; Function call
< ? php $ GLOBALS [ ' N ' ] = 4 ; function getSum ( $ r1 , $ r2 , $ c1 , $ c2 , $ dp ) { return $ dp [ $ r2 ] [ $ c2 ] - $ dp [ $ r2 ] [ $ c1 ] - $ dp [ $ r1 ] [ $ c2 ] + $ dp [ $ r1 ] [ $ c1 ] ; } function sumFound ( $ K , $ S , $ grid ) { $ dp = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ GLOBALS [ ' N ' ] ; $ i ++ ) for ( $ j = 0 ; $ j < $ GLOBALS [ ' N ' ] ; $ j ++ ) $ dp [ $ i ] [ $ j ] = 0 ; for ( $ i = 0 ; $ i < $ GLOBALS [ ' N ' ] ; $ i ++ ) for ( $ j = 0 ; $ j < $ GLOBALS [ ' N ' ] ; $ j ++ ) $ dp [ $ i + 1 ] [ $ j + 1 ] = $ dp [ $ i + 1 ] [ $ j ] + $ dp [ $ i ] [ $ j + 1 ] - $ dp [ $ i ] [ $ j ] + $ grid [ $ i ] [ $ j ] ; for ( $ i = 0 ; $ i < $ GLOBALS [ ' N ' ] ; $ i ++ ) for ( $ j = 0 ; $ j < $ GLOBALS [ ' N ' ] ; $ j ++ ) { $ sum = getSum ( $ i , $ i + $ K , $ j , $ j + $ K , $ dp ) ; if ( $ sum == $ S ) return true ; } return false ; } $ grid = array ( array ( 1 , 2 , 3 , 4 ) , array ( 5 , 6 , 7 , 8 ) , array ( 9 , 10 , 11 , 12 ) , array ( 13 , 14 , 15 , 16 ) ) ; $ K = 2 ; $ S = 14 ; if ( sumFound ( $ K , $ S , $ grid ) ) echo " Yes " ; else echo " No " ; ? >