find triangles
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...