1. ## Stabilizing Array 2D-ON

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!!

2. I'm not succeeding to figure out the recursion rule to state my solution upon it ..

3. So just to clarify - the amount of 1s in the first column must equal the amount in the 3rd, and the centre doesn't matter for a balanced matrix?

What have you tried?

4. It doesn't matter; assume that the dont care is 1(central filled with 1); we need to fill max number of 1 into the matrix and keeps it stable

5. > I've started coding the problem but I have no clue which direction to go
You stop coding, and grab a pencil and paper.

Then you keep doodling and thinking of ideas until you come up with an approach that does what you want.

Then (and only then) do you grab the keyboard and start coding.

6. about five days and I didn't arrive to any sokution before coding and then posted it here to get help ..*not helping me in code* .. In which approach to go with .. how I determine direction to go with?

7. Well it seems you need to maintain both horizontal and vertical symmetry (despite you using 'left' twice in your description).

So maybe start at opposite corners.
* * *
* * *
* * *

So you start with * then do * until you meet in the middle.

8. Originally Posted by Salem
Well it seems you need to maintain both horizontal and vertical symmetry (despite you using 'left' twice in your description).

So maybe start at opposite corners.
* * *
* * *
* * *

So you start with * then do * until you meet in the middle.
you mean I start from first * then I go to next * then I go to * so first row is visited .. and then I go to second row .. and then third row?

what do you mean until I meet in the middle?!

thanks for your help, much appreciated

9. Compare 0,0 with 2,2
Compare 0,1 with 2,1
Compare 0,2 with 2,0
Compare 1,0 with 1,2
Compare 1,1 with 1,1

10. Originally Posted by Salem

Compare 0,0 with 2,2
Compare 0,1 with 2,1
Compare 0,2 with 2,0
Compare 1,0 with 1,2
Compare 1,1 with 1,1
I got your point ! then there's no need for backtracking ..no?

11. but lets assume I have like this input matrix :
input:
- - -
1 1 1
- 0 -

the output must be :
1 - 1
1 1 1
1 0 1

the sign "-" is indicates free space (I can fill it with 1 or 0 accordingly to ensuring stabilizing) .. your concept wouldn't work on that input because I have "free spaces" so how I compare with them? thanks alot salem!!

12. My concept works fine.
Code:
```\$ ./a.out
Before
- - -
1 1 1
- 0 -
After
1 - 1
1 1 1
1 0 1```

13. Originally Posted by Salem
My concept works fine.
Code:
```\$ ./a.out
Before
- - -
1 1 1
- 0 -
After
1 - 1
1 1 1
1 0 1```
but it's not backtracking ..yeah? I mean there's no need to do backtracking .. if so, then that concept would be faster than backtracking in aspect of time complexity ..yeah? because backtracking is about doing recursive calls which they must have time complexity than the iterative approach that you suggested .

14. Originally Posted by Salem
My concept works fine.
Code:
```\$ ./a.out
Before
- - -
1 1 1
- 0 -
After
1 - 1
1 1 1
1 0 1```
1 - -
- - -
- - 0
I didn't think it will work! am I wrong? thanks alot for your help

Have you specified what should happen when 1 and 0 are opposite one another?