Given an R×C grid with each cell containing an integer, find the number of subrectangles in this grid that contain only one distinct integer; this means every cell in a subrectangle contains the same integer.
A subrectangle is defined by two cells: the top left cell (r1, c1), and the bottom-right cell (r2, c2) (1 ≤ r1 ≤ r2 ≤ R) (1 ≤ c1 ≤ c2 ≤ C), assuming that rows are numbered from top to bottom and columns are numbered from left to right.
Input
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains two integers R and C (1 ≤ R, C ≤ 1000), the number of rows and the number of columns of the grid, respectively.
Each of the next R lines contains C integers between 1 and 109, representing the values in the row.
Output
For each test case, print the answer on a single line.
Example
1 3 3 3 3 1 3 3 1 2 2 5
16 题意:问由单一数字组成的矩阵的个数。 思路： dp[i][j]表示以位置i,j为右下角的矩阵个数。 先处理出当前位置向上延伸相同的数字最高有多高。用num[i]记录。 用单调栈处理出在此之前的，第一个小于自己的num[i]. 判断中间有没有插入别的数，再进行处理。详见solve函数。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include