Skip to main content

Google

Google OA 2023 - Traingles

You are given a matrix M with n rows and m columns. The matrix only consists of either 0 or 1.

A right-angled isosceles triangle is defined as:

  • The hypotenuse has to be parallel to the x-axis.
  • The length of hypotenuse should be odd and greater than or equal to three
  • All the cells on and inside the triangle should be 0.

Task

Determine the total number of right-angled isosceles triangles, which are formed by 0.

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