CCC ’18 J4 (S2)

Matrices are among an important group in coding problems. Matrix rotations are also vital. For instance, QR codes can be read even when it is rotated 90°. Take the coding problem below as an example:

https://dmoj.ca/problem/ccc18s2

This is a matrix problem. At first glance, people might thnk that the data of plant growth needs to be literally rotated, but the result could just simply be printed out, by a corner. But first, how do you find what you need to rotate back?

The answer is to find the minimum number in the entire matrix. This number is supposed to be in the top left corner. You also may realize that the smallest number could only be in a corner.

Once you found the smallest number in the matrix, you can find what the rotation degree is, and know what the actual data should be. For example, if the minimum number is in the top right, the data was rotated 90 degrees clockwise.

Rotating a matrix is not easy, but printing the matrix as if it was already rotated is not really difficult. This is possible by reading the matrix by a corner. First try to read a matrix by all of its corners before looking down.

Example (C++):

#include <iostream>
using namespace std;
int main()
{

    int m = 3; //m rows
    int n = 3; //n columns
    int data[m][n] = {13, 27, 64, 78, 5, 31, 46, 59, 82};

    int i = 0, j = 0;

    // corner top left, reading like left to right, top to bottom

    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
        {
            cout << data[i][j] << " ";
        }
        cout << endl;
    }

    cout << endl;

    //corner top left, reading like left to right, top to bottom
    for (j = 0; j < n; j++)
    {
        for (i = 0; i < m; i++)
        {
            cout << data[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;

    //corner top right, reading like top to bottom, right to left

    for (i = 0; i < m; i++)
    {
        for (j = n; j > 0; j--)
        {
            cout << data[i][j - 1] << " ";
        }
        cout << endl;
    }
    cout << endl;

    //corner top right, reading like top to bottom, right to left

    for (j = n; j > 0; j--)
    {
        for (i = 0; i < m; i++)
        {
            cout << data[i][j - 1] << " ";
        }
        cout << endl;
    }
    cout << endl;

    //corner bottom right, reading bottom to top, right to left

    for (j = n; j > 0; j--)
    {
        for (i = m; i > 0; i--)
        {
            cout << data[i - 1][j - 1] << " ";
        }
        cout << endl;
    }
    cout << endl;

    //corner bottom right, reading bottom to top, right to left

    for (i = m; i > 0; i--)
    {
        for (j = n; j > 0; j--)
        {
            cout << data[i - 1][j - 1] << " ";
        }
        cout << endl;
    }
    cout << endl;

    //bottom left, reading bottom to top, left to right

    for (j = 0; j < n; j++)
    {
        for (i = m; i > 0; i--)
        {
            cout << data[i - 1][j] << " ";
        }
        cout << endl;
    }
    cout << endl;

    //bottom left, reading bottom to top, left to right

    for (i = m; i > 0; i--)
    {
        for (j = 0; j < n; j++)
        {
            cout << data[i - 1][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

This reads the matrix by all corners. Now, if a matrix was turned by 90°, you could print the real matrix by reading it from the top right, going down. Same goes for all the other corners, except that they are read from different corners. Using this, we can determine the final solution without actually rotating.

Example solution (C++):

#include <iostream>
using namespace std;
int main()
{

    int plants;
    cin >> plants;
    int data[plants][plants];
    for (int i = 0; i < plants; i++)
    {
        for (int x = 0; x < plants; x++)
        {
            cin >> data[i][x];
        }
    }

    int tl = data[0][0], tr = data[0][plants - 1], bl = data[plants - 1][0], br = data[plants - 1][plants - 1];

    if (tl < tr && tl < bl && tl < br)
    {
        //cout << "smallest number: top left" << endl;
        for (int i = 0; i < plants; i++)
        {
            for (int j = 0; j < plants; j++)
            {
                cout << data[i][j] << " ";
            }
            cout << endl;
        }
    }
    else if (tr < tl && tr < bl && tr < br)
    {
        //cout << "smallest number: top right" << endl;
        for (int j = plants; j > 0; j--)
        {
            for (int i = 0; i < plants; i++)
            {
                cout << data[i][j - 1] << " ";
            }
            cout << endl;
        }
    }
    else if (bl < tl && bl < tr && bl < br)
    {
        //cout << "smallest number: bottom left" << endl;
        for (int j = 0; j < plants; j++)
        {
            for (int i = plants; i > 0; i--)
            {
                cout << data[i - 1][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    else
    {
        //cout << "smallest number: bottom right" << endl;
        for (int i = plants; i > 0; i--)
        {
            for (int j = plants; j > 0; j--)
            {
                cout << data[i - 1][j - 1] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
}