l shaped plots

Problem

Given a grid of R rows and 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 1s.

An "L-shape" is defined as an unordered pair of segments, which has all the following properties:

  • Each of the segments must be a "good" segment.
  • The two segments must be perpendicular to each other.
  • The segments must share one cell that is an endpoint of both segments.
  • Segments must have length at least 2.
  • The length of the longer segment is twice the length of the shorter segment.

We need to count the number of L-shapes in the grid.

Below you can find two examples of correct L-shapes,

Examples of valid L-shapes.

and three examples of invalid L-shapes.

Examples of invalid L-shapes.

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.

Input

The first line of the input contains the number of test cases, T. T test cases follow.

The first line of each testcase contains two integers R and C.

Then, R lines follow, each line with C integers representing the cells of the grid.

Output

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 L-shapes.

Limits

Time limit: 60 seconds.
Memory limit: 1 GB.
1<=T<=100.
Grid consists of 0s and 1s only.

Test Set 1

1<=R<=40.
1<=C<=40.

Test Set 2

1<=R<=1000 and 1<=C<=1000 for at most 5 test cases.
For the remaining cases, 1<=R<=40 and 1<=C<=40.

In Sample Case #1, there is one L-shape.

  • The first one is formed by using cells: (1,1), (2,1), (3,1), (4,1), (4,2)
Visualization for the first sample case, showing one L-shape.

In Sample Case #2, there are nine L-shapes.

  • The first one is formed by using cells: (1,1), (2,1), (3,1), (4,1), (5,1), (6,1), (6,2), (6,3)
  • The second one is formed by using cells: (3,1), (4,1), (5,1), (6,1), (6,2)
  • The third one is formed by using cells: (6,1), (5,1), (4,1), (3,1), (3,2)
  • The fourth one is formed by using cells: (3,3), (4,3), (5,3), (6,3), (6,2)
  • The fifth one is formed by using cells: (6,3), (5,3), (4,3), (3,3), (3,2)
  • The sixth one is formed by using cells: (3,1), (3,2), (3,3), (3,4), (2,4)
  • The seventh one is formed by using cells: (3,4), (3,3), (3,2), (3,1), (2,1)
  • The eighth one is formed by using cells: (3,4), (3,3), (3,2), (3,1), (4,1)
  • The ninth one is formed by using cells: (6,3), (5,3), (4,3), (3,3), (3,4)
The first three L-shapes are shown on the picture below. Visualization for the second sample case, showing first three L-shapes.

Sample Input & Output

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

Rust Solution

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");

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.

L-shape 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 L-shape. 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 L-shape, 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×(|ik|+1) or |ik|+1=2×(|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×(|jl|+1) or |jl|+1=2×(|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 L-shape because there are O(R2×C2) such possible combinations. We can calculate the number of possible L-shapes with these end points in O(1). Hence, the overall complexity of the solution is O(R2×C2).

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 L-shapes 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 L-shape.

Consider a cell (i,j). There can be 4 types of L-shapes 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 L-shapes 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 L-shapes with longer segment as part of the segment with length x are min(x2,y)1. Similarly, number of L-shapes with longer segment as part of the segment with length y are min(y2,x)1. Hence, Count(x,y)=min(x2,y)+min(y2,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 L-shapes 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 L-shapes 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 L-shapes 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(R×C) time complexity. Count(i,j) can be calculate in O(R×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(R×C).

Having problems with this solution? Click here to submit an issue on github.