Matrices algorithm task

Question

I've been given a task and I tried to figure it out but I struggle with it. Any help is very appreciated and welcome. Here's the task.

It is given a square matrix with N rows. You have to find all the sums of the perimeters which are formed by the elements of every inscribed square having peak with coordinates: row index - first row and column index - respectively the rows with indexes from second to the penultimate one. Also you have to check if those sums (perimeter of the I, II, III, ... inscribed squres) are monotonous series.

---

**Edit:**

For example: if N=3 we have 3x3 matrix:

1 2 3
4 5 6
7 8 9

The inscribed square and for this example also perimeter is composed from those elements: 2-4-6-8 and P=20

for example if we have 4x4 matrix (N=4):

1   2   3   4 
5   6   7   8
9   10  11  12
13  14  15  16

There will be 2 inscribed squares :
I: 2-5-7-10 with P=19
II: 3-6-8-11 with P=28

and so on

---

Here is my draft if that could be in help

And here is the code I have created so far:

    #include <iostream>

    using namespace std;

    #define N 6
    #define M 6

    int main()
    {

        int i, j , arr[N][M];
        int squaresInSquare = 0;
    /*
        cout << "Input the elements of the two dimensional array: \n\n";

        for(i=0; i<N; i++)
        {
            for(j=0; j<M; j++)
            {
                cout << "arr[" << i << "][" << j << "] = ";
                cin >> arr[i][j];
            }
        }



    //Comment these 2 loops if you want speed
    for(i=0; i<N; i++)
        {
            for(j=0; j<M; j++)
            {
                cout << arr[i][j] << "\t";
            }
            cout << "\n";
        }
     cout << endl <<endl;
    */


    // The next if-else determines how many inscribed squares we have
    if(N%2==0)
    {
        //N is an even number
        int temp = N;

        while(temp!=2)
        {
            temp -= 2;
            squaresInSquare += temp;
        }
        cout << "The inscribed squares are: " << squaresInSquare;
    }
    else
    {
        //N is an odd number
        int temp = N;

        while(temp!=1)
        {
            temp -= 2;
            squaresInSquare += temp;
        }
        cout << "The inscribed squares are: " << squaresInSquare;
    }



    int arrSums [squaresInSquare]; // this array holds the sums for every inscribed square perimeter
    for(i=0; i<squaresInSquare; i++)
    {
        //here we reset the elements to 0
        arrSums[i] = 0;
    }


    squaresInSquare = 0;


    if(N==1 || N==2)
    {
            cout << "There are no inscribed squares";
            return 0;
    }
    else if(N>=3)
    {
        if(N%2==0)
        {
            //N is an even number
            int temp = N;
            int k = 0;
            int step = 0;
            i=1;
            while(temp!=2)
            {
                temp -= 2;
                squaresInSquare += temp; // squaresInSquare can be: 2; 4+2; 6+4+2 ...     N + (N-2) + ((N-2)-2)


                for(i; i<=N-i; i++)
                {

                    arrSums[k] += arr[i][]

    ??????????????????????????????????????????????


                k++;
                }
                i=i+1;



            }

        }
        else
        {
            //N is an odd number


TODO first the algorithm for even numbers and then correct it for odd

            int temp = N;

            while(temp!=1)
            {
                temp -= 2;
                squaresInSquare += temp;
            }
            cout << "The inscribed squares are:  " << squaresInSquare;
        }


    }
        return 0;
    }

Answer 1

Iterate through the sizes. For each size s, the upper vertices of the inscribed squares are [s+1, ..., N-s]. For example, when N=7 and s=2, the upper vertices of the inscribed squares (of that size) are [3,4,5].

The next trick is to take diagonal steps in the matrix. When N=7:

 1  2  3  4  5  6  7
 8  9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35
36 37 38 39 40 41 42
43 44 45 46 47 48 49

from point 17, you can move down-and-left to 23, or down-and-right to 25. Figure out the rule: given N and a starting point k, what is the formula for the two points below k (one down-and-left, the other down-and-right)?

Once you have those steps, the rest is easy. (Don't forget to test your code at every step.)