numberOfRightTriangle

Victor vừa được học về tam giác vuông, cậu đang tập nhận biết chúng bằng cách sau: Vẽ một ma trận n * m (n dòng, m cột) gồm các khoảng trắng (-) và các điểm (X), mỗi ba điểm sẽ tạo ra các tam giác khác nhau nhưng do không có dụng cụ đo đạc và trí tưởng tượng kém nên Victor chỉ xét những tam giác có 2 cạnh vuông góc hoặc song song với các cạnh của ma trận thì mới tính đó là một tam giác vuông. Do số lượng tam giác vuông xuất hiện quá nhiều và Victor không thể đếm hết nên đành nhờ bạn đếm hộ. Cho ma trận n * m, hãy đếm tất cả các tam giác vuông thỏa điều kiện của Victor đề ra.

Ví dụ:

• Với n = 3, m = 3, s = ["X-X","-X-","X--"] thì number_of_right_triangle(n, m, s) = 1.
  Giải thích:
  • Ta có bộ ba điểm s[1][1] - s[1][3] - s[3][1] tạo thành một tam giác vuông.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5 giây với C++, 3 giây với Java và C#, 4 giây với Python, Go và Js

• [Đầu vào] Integer n, Integer m
  1 ≤ n, m ≤ 1000

• [Đầu vào] Array of String s
  s.size = n
s[i].length = m

• [Đầu ra] Long
  Số lượng tam giác vuông thỏa điều kiện đếm được.