Isosceles Triangles

mail@pastecode.io avatar
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;
	}
};