Hi guys !
I really in need for help; I'm not new in C programming but still having gaps!
I've a problem in dynamic programming which given a matrix with N*N size which I've to add ones to the matrix to be stable. to be stable must satisfied those two rules: (( assuming weight is the sum of number 1))
1) its left and right halves must carry the same weight
also
2)its front and left halves must carry the same weight
for example: lets assume I have this matrix(As an input):
1 1 1
0 0 0
1 1 1
for first condition(rule), the half is the second column, this matrix is stable because the first column weight (3) is the same weight as the third column which's also 3.
for second condition(rule), the half is the second row, the first row is weighting "3-number of ones" the same as the third row which it's also weight 3. So, the matrix is called stable!
Second example:
lets assume I have this matrix
1 - -
0 0 0
- 1 -
I've to fill the matrix with maximum weight (fill maximum number of ones) that can ensure the matrix will be stable(stable means
satisfying the two conditions respectively) - by the way for filling the matrix in my second example .. the output must be the the same matrix on the first example because it's the maximal way to stable the matrix ..
third example: lets assume the given input matrix is:
- - -
- - -
0 0 -
then I need to assign into that matrix max number of ones that can ensure stabilization of my matrix, for third example the output must be:
1 - -
1 1 1
0 0 1
the "-" is free space or whatever neglected value "-1" .. doesn't matter ..
Any help please? I've started coding the problem but I have no clue which direction to go, how to think about it properly !
I want solve it in an optimal way and not in iterative way!!
thanks alot for your cooperative!!