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\)
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
Editorial