http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2465
Recursion method is used to solve this problem.
First of all, get the size of the grid. Even and odd number of the size will have some slightly different in the coding part especially the inner square.
Taking odd grid as example given in the question:
| 5 | 3 | 2 | 7 | 9 |
| 1 | 7 | 4 | 2 | 4 |
| 5 | 3 | 2 | 4 | 6 |
| 1 | 3 | 4 | 5 | 1 |
| 1 | 4 | 5 | 6 | 3 |
First of all, get the sum of outer most square.
5 + 3 + 2 + 7 + 9 + 1 + 4 + 5 + 6 + 1 + 1 + 1 + 4 + 5 + 6 + 3 = 63
In order to get the sum of this square, I get the sum for each row and column separately in the square.
| 5 | 3 | 2 | 7 | 9 |
| 1 | 7 | 4 | 2 | 4 |
| 5 | 3 | 2 | 4 | 6 |
| 1 | 3 | 4 | 5 | 1 |
| 1 | 4 | 5 | 6 | 3 |
5 + 3 + 2 + 7 + 9 = 26
| 5 | 3 | 2 | 7 | 9 |
| 1 | 7 | 4 | 2 | 4 |
| 5 | 3 | 2 | 4 | 6 |
| 1 | 3 | 4 | 5 | 1 |
| 1 | 4 | 5 | 6 | 3 |
5 + 1 + 5 + 1 + 1 =13
| 5 | 3 | 2 | 7 | 9 |
| 1 | 7 | 4 | 2 | 4 |
| 5 | 3 | 2 | 4 | 6 |
| 1 | 3 | 4 | 5 | 1 |
| 1 | 4 | 5 | 6 | 3 |
9 + 4 + 6 + 1 + 3 = 23
| 5 | 3 | 2 | 7 | 9 |
| 1 | 7 | 4 | 2 | 4 |
| 5 | 3 | 2 | 4 | 6 |
| 1 | 3 | 4 | 5 | 1 |
| 1 | 4 | 5 | 6 | 3 |
1 + 4 + 5 + 6 + 3 = 19
After that, sum up each row and column in square.
26 + 13 + 23 + 19 = 81
It stills not the correct answer yet, because we have to subtract out the intersection for in each row and column.
| 5 | 3 | 2 | 7 | 9 |
| 1 | 7 | 4 | 2 | 4 |
| 5 | 3 | 2 | 4 | 6 |
| 1 | 3 | 4 | 5 | 1 |
| 1 | 4 | 5 | 6 | 3 |
81 – ( 5 + 1 + 9 + 3 ) = 63
Now we got the sum of the outer most square and output it. We proceed to the 2nd outer most square where we reduced it to a smaller grid.
| 7 | 4 | 2 |
| 3 | 2 | 4 |
| 3 | 4 | 5 |
Same method as above is used, get the sum of each row and columns, then subtract out the intersection. The grid keep reduce and same steps keep repeat until we reach the most inner square. The most inner square is our base case in this recursion.
There are 2 type of the most inner square:
- Odd grid will only has 1 number in the most inner square
- Even grid will has 4 numbers in the most inner square as below :
| 2 | 4 |
| 4 | 5 |
Get the sum of the most inner square (for even) or output the only number (for odd) in the base case of the recursion.
P/S : Recursion is not the only method that able to solve this problem, using the loop will able to solve the problems as well.
