Given two n x n grids composed of @ and -, determine the minimal transformation—from a predefined set—that converts the initial grid into the target grid. If multiple transformations apply, select the one with the smallest index.

Allowed Transformations

1. Clockwise 90° rotation
2. Clockwise 180° rotation
3. Clockwise 270° rotation
4. Horizontal reflection (mirror across vertical centerline)
5. Reflection followed by a rotation (rotation among types 1–3)
6. No change
7. Invalid (none of the above matches)

Only one transformation step from the list may be used.

Input Format

• First line: integer n (grid dimension).
• Next n lines: initial grid.
• Following n lines: target grid.

Characters are limited to @ and -.

Output Format

A single digit 1–7 indicating the matching transformation.

Implementation Details

Store grids in 2D arrays indexed from 0 to n-1 for simplicity. Perform checks in order from transformation 1 to 6; if none match, output 7.

Rotation Logic

Let orig be the source grid and dest the pattern to compare with.

• 90° clockwise: dest[r][c] = orig[n-1-c][r]
• 180°: dest[r][c] = orig[n-1-r][n-1-c]
• 270° clockwise: dest[r][c] = orig[c][n-1-r]

Horizontal Reflection

Mirror each row: dest[r][c] = orig[r][n-1-c]

Combined Reflection + Rotation

First reflect horizontally, then test for 90°, 180°, or 270° rotations.

No Change

Direct cell-by-cell equality check between orig and dest.

Example

Input:

3
@-@
---
@@-
@-@
@--
--@

Output:

1

Code Example

#include <iostream>
#include <vector>
using namespace std;

int dim;
vector<string> start, goal;

bool check_90() {
    for (int r = 0; r < dim; r++) {
        for (int c = 0; c < dim; c++) {
            if (goal[r][c] != start[dim - 1 - c][r])
                return false;
        }
    }
    return true;
}

bool check_180() {
    for (int r = 0; r < dim; r++) {
        for (int c = 0; c < dim; c++) {
            if (goal[r][c] != start[dim - 1 - r][dim - 1 - c])
                return false;
        }
    }
    return true;
}

bool check_270() {
    for (int r = 0; r < dim; r++) {
        for (int c = 0; c < dim; c++) {
            if (goal[r][c] != start[c][dim - 1 - r])
                return false;
        }
    }
    return true;
}

bool check_reflect() {
    for (int r = 0; r < dim; r++) {
        for (int c = 0; c < dim; c++) {
            if (goal[r][c] != start[r][dim - 1 - c])
                return false;
        }
    }
    return true;
}

bool check_combo() {
    vector<string> reflected(dim, string(dim, ' '));
    for (int r = 0; r < dim; r++)
        for (int c = 0; c < dim; c++)
            reflected[r][c] = start[r][dim - 1 - c];

    // test 90 on reflected
    for (int r = 0; r < dim; r++) {
        for (int c = 0; c < dim; c++) {
            if (goal[r][c] != reflected[dim - 1 - c][r])
                goto rot180;
        }
    }
    return true;
rot180:
    // test 180 on reflected
    for (int r = 0; r < dim; r++) {
        for (int c = 0; c < dim; c++) {
            if (goal[r][c] != reflected[dim - 1 - r][dim - 1 - c])
                goto rot270;
        }
    }
    return true;
rot270:
    // test 270 on reflected
    for (int r = 0; r < dim; r++) {
        for (int c = 0; c < dim; c++) {
            if (goal[r][c] != reflected[c][dim - 1 - r])
                return false;
        }
    }
    return true;
}

bool check_same() {
    for (int r = 0; r < dim; r++)
        for (int c = 0; c < dim; c++)
            if (goal[r][c] != start[r][c])
                return false;
    return true;
}

int main() {
    cin >> dim;
    start.resize(dim);
    goal.resize(dim);
    for (int i = 0; i < dim; i++)
        cin >> start[i];
    for (int i = 0; i < dim; i++)
        cin >> goal[i];

    if (check_90())          cout << "1\n";
    else if (check_180())     cout << "2\n";
    else if (check_270())     cout << "3\n";
    else if (check_reflect()) cout << "4\n";
    else if (check_combo())   cout << "5\n";
    else if (check_same())    cout << "6\n";
    else                     cout << "7\n";

    return 0;
}