find triangles

 avatar
unknown
c_cpp
2 years ago
1.1 kB
6
Indexable
int find_triangles(int n, int m, vector<string> M){

        int dp[n][m][m];

        memset(dp, 0, sizeof(dp));

        int res = 0;

        for(int i=0, j=0; j<m; ++j){
            if(M[i][j]=='0')
            dp[i][j][j] = 1;
        }

        for(int i=1; i<n; ++i){
            for(int j = 0; j<m; ++j){
                if(M[i][j]=='0')
                for(int k = j+1; k<m; ++k){
                    if(M[i][k]=='0'){
                        if((k-j)%2==0){
                            if(dp[i-1][j+1][k-1]==1){
                                dp[i][j][k] = 1;
                                res++;
                            }
                        }
                    } else {
                        for(int l = j; l<k-1; ++l){
                            if(dp[i-1][l+1][k-2]==1){
                                dp[i][l][k-1] = 1;
                                res++;
                            }
                        }
                        j=k+1;
                        break;
                    }
                }
            }
        }

        return res;

    }
Editor is loading...