A grid
Practice
5 (1 votes)
Introduction to dynamic programming 2
Algorithms
Dynamic programming
Problem
84% Success 476 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

You are given a grid $$A$$ that consists of $$N$$ rows and $$M$$ columns. Each number in the grid is either $$0$$ or $$1$$. 

Calculate the number of such triples \((i, j, h)\) where for all the pairs \((x, y)\), both $$x$$ and $$y$$ belong to \([1, h]\) if \(y >= x\) and \(A[i+x-1][j+y-1]\) equals to $$1$$. Of course, the square \((i, j, i+h-1, j+h-1)\) should be inside of this grid. In other words, calculate the count of square submatrices of the given grid $$A$$ which have their value equal to $$1$$ for every element present on and above their main diagonal.

Input format

  • The first line contains an integer $$T$$ denoting the number of test cases.
  • The first line of each testcase contains two space-separated integers $$N$$ and $$M$$ denoting the size of the grid $$A$$.
  • The following $$N$$ lines describe the grid. Each line consists of $$M$$ characters that are either $$0$$ or $$1$$.

Output format

For each test case, print the count of square submatrices in a new line.

Constraints

\(1 \le T \le 10\\ 1 \le N,M \le 3000\)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
Tags:
mediumDynamic programmingArrays2dIntroduction to Dynamic Programming-2AlgorithmsMediumDynamic Programming
Points:30
Tags:
Medium
Points:30
11 votes
Tags:
BitmaskDynamic ProgrammingAlgorithmsApprovedMedium