Skip to main content

Posts

Showing posts with the label Count Square Submatrices with All Ones

MAY-21 2020 Challenge

Count Square Submatrices with All Ones Given a m * n matrix of ones and zeros, return how many square submatrices have all ones. Example 1: Input: matrix = [   [0,1,1,1],   [1,1,1,1],   [0,1,1,1] ] Output: 15 Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15 . Example 2: Input: matrix = [ [1,0,1], [1,1,0], [1,1,0] ] Output: 7 Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 + 1 = 7 . Constraints: 1 <= arr.length <= 300 1 <= arr[0].length <= 300 0 <= arr[i][j] <= 1 Solution in C++ class Solution { public:     int n,m,cnt=0;     int mat[302][302],dp[302][302];     int  dfs(int i,int j)     {         if(i>=n||j>=m)             return 0; ...