Skip to main content

Google

Google OA-4 2023

Problem Description

You are presented with a matrix M that contains n rows and m columns, filled exclusively with 0's and 1's. A right-angled isosceles triangle is defined by the following criteria:

  • The hypotenuse must be parallel to the x-axis.
  • The length of the hypotenuse must be odd and at least three.
  • All cells within and on the boundary of the triangle must contain 0.

Task:
Calculate the total number of right-angled isosceles triangles that can be formed using 0's in the matrix.

Example

The grid is given as:

Graphic designer needed

Approach

Function Description

Complete the find_triangles function provided in the editor. This function takes the following 3 parameters and returns the total number of isosceles right-angles angles:

  • n: Represents the number of rows in the matrix
  • m: Represents the number of columns in the matrix
  • M: Represents the matrix

Input Format

Note: This is the input format you must use to provide custom input

  • The first line contains one integer T denoting the number of test cases.T also specifies the number of times you have to run the find triangles function on a different set of inputs.
  • For each test case:
  • The first line contains an integer n representing the number of rows of the matrix.
  • The second line contains an integer m representing the number of columns of the matrix.
  • The next n lines contain a string of length m representing a row,

Output format

For each test case, print an integer in a new line representing the number of right
angled isosceles triangles.

Sample Input

Sample Output

Explanation: The first line states the number of test cases. Therefore T=2.

The first test case
The input is:

The second test case

It is explained in the above example