# Isosceles Triangles

unknown
c_cpp
a year ago
1.4 kB
1
Indexable
Never
```#include<vector>
class IsoscelesTriangles {
public:
long getNumberOfTriangles(int n, int m, std::vector<std::vector<int>> M) {
int i, j;
std::vector<std::vector<int>>dp_up(n, std::vector<int>(m, 0)); // store number of triangles facing up
std::vector<std::vector<int>>dp_down(n, std::vector<int>(m, 0)); // store number of triangles facing down
int ans = 0;
for(i=n-1;i>=0;i--){
for(j=m-1;j>=0;j--){
// assign the dp as 1 if matrix is 0 at the current point
if(!M[i][j])dp_up[i][j] = 1;

// if the current point lies in first or last column or last row then no triangle facing up exists
if(i == n-1 || j == 0 || j == m-1)continue;

else if(!M[i][j]){
dp_up[i][j] = std::min(std::min(dp_up[i+1][j-1],dp_up[i+1][j]), dp_up[i+1][j+1]) + 1;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
// assign the dp as 1 if matrix is 0 at the current point
if(!M[i][j])dp_down[i][j] = 1;

// if the current point lies in first or last column or first row then no triangle facing down exists
if(i == 0 || j == 0 || j == m-1)continue;

else if(!M[i][j]){
dp_down[i][j] = std::min(std::min(dp_down[i-1][j-1],dp_down[i-1][j]), dp_down[i-1][j+1]) + 1;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(!M[i][j])ans += (dp_up[i][j] + dp_down[i][j] - 2);
}
}
return ans;
}
};
```