C++ Transformation of Square Patterns [USACO1.2]

Click the blue text

Follow us

P1205 [USACO1.2] Transformation of Square Patterns

Problem Description

A pattern of black and white tiles in an n×n square needs to be transformed into a new square pattern. Write a program to find the minimum way to transform the original pattern into the new pattern using the following transformation methods:

• Rotate 90°: Rotate the pattern 90° clockwise.

• Rotate 180°: Rotate the pattern 180° clockwise.

• Rotate 270°: Rotate the pattern 270° clockwise.

• Reflect: Flip the pattern horizontally (creating a mirror image of the original pattern along the central vertical line).

• Combination: Reflect the pattern horizontally, then apply one of the transformations from 1 to 3.

• No Change: The original pattern remains unchanged.

• Invalid Transformation: The new pattern cannot be obtained using the above methods.

If there are multiple available transformation methods, choose the one with the smallest number.

Only use one of the seven steps mentioned above to complete this transformation.

Input Format

The first line contains a positive integer n.

Then n lines, each containing n characters, all being @ or -, representing the initial square.

Next, n lines, each containing n characters, all being @ or -, representing the final square.

Output Format

A single line containing a number between 1 and 7 (as described above) indicating the transformation method needed to change the original square into the transformed square.

Input Example

#1

3@-@—@@-@-@@–

Output Example

#1

1

Explanation/Hint

For 100% of the data, 1≤n≤10.

💡 Problem Analysis

Given two $$n×n$$ black and white patterns (where @ represents black and – represents white), we need to find the minimum transformation method number to convert the original pattern into the new pattern. The transformation methods include:

1. Rotate 90°: Rotate 90° clockwise

2. Rotate 180°: Rotate 180° clockwise

3. Rotate 270°: Rotate 270° clockwise

4. Reflect: Flip horizontally (mirror along the vertical centerline)

5. Combination: Reflect + Rotate (90°/180°/270°)

6. No Change: The original pattern remains unchanged

7. Invalid Transformation: Cannot be transformed using the above methods

💡 Solution Approach

01

Core Transformation Operations:

• Rotate 90°: Achieved through coordinate transformation: position $(i, j)$ →

• Horizontal Reflection: position →

• Rotate 180° = Rotate 90° × 2

• Rotate 270° = Rotate 90° × 3

02

Check Order:

• Check in order of transformation number from smallest to largest (1→7)

• Once a valid transformation is found, return immediately to ensure the smallest number

• Combination operation check: Perform three rotations (90°/180°/270°) after reflection

03

Matrix Comparison:

• Compare each element of the original matrix with the target matrix

• Use memory-friendly matrix representation (avoid copying large matrices)

Mathematical Principles

• Matrix Rotation: Coordinate transformation for rotation angle:

• 90° rotation: (x,y) → (y, n-1-x)

• Reflection Transformation:(x,y) → (x, n-1-y)

• Transformation Combination: Reflection + Rotation = Composite operation of linear transformations

Code Implementation

#include<iostream>#include<vector> // Use vector to store dynamic matrixusing namespace std;/** * Compare two matrices for equality * @param a First matrix (row-major storage) * @param b Second matrix * @param n Matrix dimension (n×n) * @return Returns true if equal, otherwise false */bool areMatricesEqual(const vector<vector<char>>& a, const vector<vector<char>>& b, int n) {    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            if (a[i][j] != b[i][j])                 return false;        }    }    return true;} /** * Matrix transformation for clockwise rotation by 90 degrees * @param a Original matrix * @param n Matrix dimension * @return New matrix after rotation * * Mathematical principle: coordinate transformation (i, j) → (j, n-1-i) */vector<vector<char>> rotate90(const vector<vector<char>>& a, int n) {    // Create n×n result matrix    vector<vector<char>> res(n, vector<char>(n));        for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            // Core rotation transformation: original element a[i][j] moves to new position [j][n-1-i]            res[j][n - 1 - i] = a[i][j];        }    }    return res;} /** * Horizontal reflection transformation (mirror along the vertical centerline) * @param a Original matrix * @param n Matrix dimension * @return New matrix after reflection * * Mathematical principle: coordinate transformation (i, j) → (i, n-1-j) */vector<vector<char>> reflect(const vector<vector<char>>& a, int n) {    vector<vector<char>> res(n, vector<char>(n));        for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            // Core reflection: original element a[i][j] moves to new position [i][n-1-j]            res[i][n - 1 - j] = a[i][j];        }    }    return res;}int main(){    int n;    cin >> n;  // Read matrix size    // Initialize original and target matrices    vector<vector<char>> original(n, vector<char>(n));    vector<vector<char>> target(n, vector<char>(n));    // Read original matrix (n rows of strings)    for (int i = 0; i < n; i++) {        string row;        cin >> row;        for (int j = 0; j < n; j++) {            original[i][j] = row[j];  // Store character        }    }    // Read target matrix (n rows of strings)    for (int i = 0; i < n; i++) {        string row;        cin >> row;        for (int j = 0; j < n; j++) {            target[i][j] = row[j];  // Store character        }    }    // Transformation method 1: Rotate 90°    vector<vector<char>> r90 = rotate90(original, n);    if (areMatricesEqual(r90, target, n)) {        cout << 1 << endl;        return 0;    }    // Transformation method 2: Rotate 180° (= Rotate 90°×2)    vector<vector<char>> r180 = rotate90(r90, n);    if (areMatricesEqual(r180, target, n)) {        cout << 2 << endl;        return 0;    }    // Transformation method 3: Rotate 270° (= Rotate 90°×3)    vector<vector<char>> r270 = rotate90(r180, n);    if (areMatricesEqual(r270, target, n)) {        cout << 3 << endl;        return 0;    }    // Transformation method 4: Horizontal Reflection    vector<vector<char>> reflected = reflect(original, n);    if (areMatricesEqual(reflected, target, n)) {        cout << 4 << endl;        return 0;    }    // Transformation method 5: Reflection + Rotation (90°/180°/270°)    // First perform reflection    vector<vector<char>> comp = reflected;    // Try three rotations    for (int i = 0; i < 3; i++) {        comp = rotate90(comp, n);  // Perform rotation 90°×(i+1) times        if (areMatricesEqual(comp, target, n)) {            cout << 5 << endl;            return 0;        }    }    // Transformation method 6: No Change    if (areMatricesEqual(original, target, n)) {        cout << 6 << endl;        return 0;    }    // Transformation method 7: Invalid Transformation    cout << 7 << endl;    return 0;}

Click below to read the original text

Direct access to the Luogu problem bank for practice

Key Function Descriptions:

areMatricesEqual()

• Function: Element-wise comparison of two matrices

• Time Complexity:

rotate90()

• Core Operation: res[j][n-1-i] = a[i][j]

• Space Usage: Creates a new matrix ()

reflect()

• Core Operation: res[i][n-1-j] = a[i][j]

• Space Usage: Creates a new matrix ()

🛠️ Library and Function Usage Instructions

• <iostream>: C++ standard input-output stream library for reading and writing data.

• cin: Reads standard input.

• cout: Outputs data to standard output.

• <vector>: C++ standard container library for storing dynamic arrays.

• vector<vector<char>>: Two-dimensional matrix (row-major storage)

• vector(n, value): Constructs a vector containing n elements of value for processing.

Key Terms in the Code

vector

• C++ dynamic array container

char

• Stores a single character (@/-)

res

• Abbreviation for result (matrix storing results)

comp

• Abbreviation for composite (result of combination operation)

💻 Usage Instructions

Input Format:

• First line: Integer n (matrix size)

• Next n lines: Original matrix (each line of characters)

• Subsequent n lines: Target matrix (each line of characters)

Output Format:

• A single integer (1~7) indicating the minimum transformation number

Execution Example:

Input Example

3@-@—@@-@-@@––@

Output

1

Performance:

• Time Complexity:O(n²) (matrix operations are linear)

• Space Complexity:O(n²) (stores intermediate matrices)

END

Like

Collect

Share

Explore the forefront of educational technology, empowering future learning!

“Bit Island Education Technology” is committed to using innovative technology to create a more efficient, engaging, and future-oriented learning experience.

• Get the latest educational technology products and course materials

• Learn practical and effective learning methods and educational concepts

• Discover innovative teaching tools and classroom application cases

• Participate in exclusive events and win learning benefits

Scan the code to follow us and start your journey in smart education!👇

BIT ISLAND

Long press to scan

WeChat ID丨bit_island_Terry

WeChat Search丨Bit Island Education Technology