Given a grid of $\mathbf{R}$ rows and $\mathbf{C}$ columns each cell in the grid is either $0$ or $1$.
A segment is a nonempty sequence of consecutive cells such that all cells are in the same row or the same column. We define the length of a segment as number of cells in the sequence.
A segment is called "good" if all the cells in the segment contain only $1$s.
An "Lshape" is defined as an unordered pair of segments, which has all the following properties:
We need to count the number of Lshapes in the grid.
Below you can find two examples of correct Lshapes,
and three examples of invalid Lshapes.
Note that in the shape on the left, two segments do not share a common endpoint. The next two shapes do not meet the last requirement, as in the middle shape both segments have the same length, and in the last shape the longer segment is longer than twice the length of the shorter one.
The first line of the input contains the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.
The first line of each testcase contains two integers $\mathbf{R}$ and $\mathbf{C}$.
Then, $\mathbf{R}$ lines follow, each line with $\mathbf{C}$ integers representing the cells of the grid.
For each test case, output one line containing Case #$x$: $y$
, where $x$ is
the test case number (starting from 1) and $y$ is the number of Lshapes.
Time limit: 60 seconds.
Memory limit: 1 GB.
$1<=\mathbf{T}<=100$.
Grid consists of $0$s and $1$s only.
$1<=\mathbf{R}<=40$.
$1<=\mathbf{C}<=40$.
$1<=\mathbf{R}<=1000$ and $1<=\mathbf{C}<=1000$ for at most $5$ test cases.
For the remaining cases, $1<=\mathbf{R}<=40$ and $1<=\mathbf{C}<=40$.
In Sample Case #1, there is one Lshape.
In Sample Case #2, there are nine Lshapes.
2 4 3 1 0 0 1 0 1 1 0 0 1 1 0 6 4 1 0 0 0 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0
Case #1: 1 Case #2: 9
Analysis
Test set 1
In order to verify that a segment is good, we need to check whether all the cells in that segment
contain $1$ or not.
To check whether all the cells in a segment contain $1$ or not, we can calculate prefix sum of
the matrix and then check whether sum of cells on this segment is equal to the length of the
segment or not. Let $query(a,b,c,d)$ denote the sum of cells in submatrix with $(a,b)$ as top left corner
and $(c,d)$ as bottom right corner. We can calculate
this sum in $O(1)$ using the prefix sum matrix. For more details on using prefix sum to calculate sum
of cells on a submatrix, please refer
this.
In order to get the sum of cells on segment from $(i,j)$ to $(i,l)$, we can simply check if $query(i,j,i,l)=jl+1$.
Lshape comprises of two segments which meet at a common point.
Except the common point, consider the other end point of one segment as $(i,j)$ and the end point of the other segment as $(k,l)$. Now
these end points could meet at either $(i,l)$ or $(k,j)$ to
form an Lshape. So, if we know the end points of each segment, we can figure out the common point
where segments would meet.
For each pair of end points $(i,j)$ and $(k,l)$ of segments of Lshape, we already saw that there could be $2$ possible meeting points.

For segments meeting at $(i,l)$, check that
$query(i,j,i,l)=jl+1$ and $query(k,l,i,l)=ik+1$.
Besides, either $jl+1=2\times (ik+1)$ or $ik+1=2\times (jl+1)$ should be true.
If these conditions are satisfied, increase the answer by $1$.

For segments meeting at $(k,j)$, check that
$query(i,j,k,j)=ik+1$ and $query(k,l,k,j)=jl+1$.
Besides, either $ik+1=2\times (jl+1)$ or $jl+1=2\times (ik+1)$ should be true.
If these conditions are satisfied, increase the answer by $1$.
We can iterate over all possible end points of these two segments Lshape because there
are $O({\mathbf{R}}^{2}\times {\mathbf{C}}^{2})$ such possible combinations. We can calculate the number of possible Lshapes with these end points in $O(1)$. Hence, the overall complexity of the solution is $O({\mathbf{R}}^{2}\times {\mathbf{C}}^{2})$.
Test set 2
We cannot iterate over all possible end points of the segments for this test set as the solution
would time out. If for each cell, we can quickly calculate how many Lshapes are such that both of its segments
meet at this cell, we can iterate over each cell of the matrix only once and calculate our answer. We can safely ignore those cells that
have value 0 as they cannot be part of any Lshape.
Consider a cell $(i,j)$.
There can be 4 types of Lshapes that have both of its segments meet this cell.
 Type 1: One of the segments is to top of $(i,j)$, and other segment is to the right of $(i,j)$.
 Type 2: One of the segments is to top of $(i,j)$, and other segment is to the left of $(i,j)$.
 Type 3: One of the segments is to bottom of $(i,j)$, and other segment is to the right of $(i,j)$.
 Type 4: One of the segments is to bottom of $(i,j)$, and other segment is to the left of $(i,j)$.
Let $Count(x,y)$ be the number of Lshapes with both its segments meeting at a particular point of which the length of the segment
parallel to one axis is $x$
and the length of the segment parallel to the other axis is $y$. Number of Lshapes with longer segment as part of the segment with length $x$ are
$min(\frac{x}{2},y)1$. Similarly, number of Lshapes with longer segment as part of the segment with length $y$ are
$min(\frac{y}{2},x)1$. Hence, $Count(x,y)=min(\frac{x}{2},y)+min(\frac{y}{2},x)2$.
If we can calculate number of consecutive cells that have value 1 in each side of $(i,j)$, we can calculate number of Lshapes of each type with this cell as the common endpoint of the segments using the $Count()$ function above.
Let $top(i,j)$ denote the number of consecutive cells that have value 1 including $(i,j)$ and cells above it. For cells with value 0,
$top(i,j)=0$.
Formally for cells with value 1, $top(i,j)=ik+1$ where
$1<=k<=i$ and k is least possible value such that all cells from $(k,j)$ to $(i,j)$ have value 1.
Similarly, we can define $bottom(i,j)$, $left(i,j)$ and $right(i,j)$ denoting maximum number
of consecutive cells on bottom, left and right of $(i,j)$ respectively.
We can calculate $top(i,j)$ and $left(i,j)$ by iterating from the starting of the matrix and updating their values. Refer to the code
below to calculate these values.
for(int i = 1; i <= R; i++) {
for(int j = 1; j <= C; j++) {
if (matrix[i][j] == 0) continue;
top[i][j] = top[i  1][j] + 1;
left[i][j] = left[i][j  1] + 1;
}
}
Similarly, we can calculate $bottom(i,j)$ and $right(i,j)$ by iterating from the end of
the matrix. After knowing these values, we can calculate number of Lshapes of each type for
cell $(i,j)$. $Count(top(i,j),right(i,j))$, $Count(top(i,j),left(i,j))$,
$Count(bottom(i,j),right(i,j))$ and $Count(bottom(i,j),left(i,j))$ denote the number of Lshapes of type 1, 2, 3 and 4
respectively. Thus, for each cell we can add $Count(top(i,j),left(i,j))+Count(top(i,j),right(i,j))+Count(bottom(i,j),left(i,j))+Count(bottom(i,j),right(i,j))$ to the answer.
$top(i,j)$, $bottom(i,j)$, $left(i,j)$ and $right(i,j)$ can be calculated in $O(\mathbf{R}\times \mathbf{C})$ time complexity.
$Count(i,j)$ can be calculate in $O(\mathbf{R}\times \mathbf{C})$ time complexity. Finally, we need to iterate over each cell of the matrix, and we
can update the answer in $O(1)$ for each cell. Thus, the overall complexity of the solution is $O(\mathbf{R}\times \mathbf{C})$.
use rustgym_util::*;
use std::fmt::Write;
use std::io::*;
fn solve(case_no: usize, reader: &mut impl BufRead, writer: &mut impl Write) {
let args = reader.parse_vec();
let r = args[0];
let c = args[1];
let a: Vec<Vec<i32>> = reader.parse_mat(r);
let mut up: Vec<Vec<usize>> = vec![vec![0; c]; r];
let mut left: Vec<Vec<usize>> = vec![vec![0; c]; r];
let mut down: Vec<Vec<usize>> = vec![vec![0; c]; r];
let mut right: Vec<Vec<usize>> = vec![vec![0; c]; r];
for i in 0..r {
for j in 0..c {
if a[i][j] == 1 {
up[i][j] = 1;
left[i][j] = 1;
if i > 0 {
up[i][j] += up[i  1][j];
}
if j > 0 {
left[i][j] += left[i][j  1];
}
}
}
}
for i in (0..r).rev() {
for j in (0..c).rev() {
if a[i][j] == 1 {
down[i][j] = 1;
right[i][j] = 1;
if i + 1 < r {
down[i][j] += down[i + 1][j];
}
if j + 1 < c {
right[i][j] += right[i][j + 1];
}
}
}
}
let mut res = 0;
for i in 0..r {
for j in 0..c {
res += count(up[i][j], left[i][j]);
res += count(up[i][j], right[i][j]);
res += count(down[i][j], left[i][j]);
res += count(down[i][j], right[i][j]);
}
}
writeln!(writer, "Case #{}: {}", case_no, res).unwrap();
}
fn count(a: usize, b: usize) > usize {
let x = (a / 2).min(b);
let y = (b / 2).min(a);
let mut res = 0;
if x > 1 {
res += x  1;
}
if y > 1 {
res += y  1;
}
res
}
google_test_gen!(test, "input.txt", "output.txt");