P1205 [USACO1.2] Transformations

A black-and-white pattern on an $n \times n$ square of tiles is to be transformed into a new square pattern. Write a program to find the minimal method to convert the original pattern into the new one using the following transformations: - Rotate $90\degree$: Rotate the pattern $90\degree$ clockwise. - Rotate $180\degree$: Rotate the pattern $180\degree$ clockwise. - Rotate $270\degree$: Rotate the pattern $270\degree$ clockwise. - Reflect: Flip the pattern horizontally (mirror over the central vertical line). - Combination: First reflect horizontally, then apply one of the transformations in $1 \sim 3$. - No change: The original pattern is unchanged. - Invalid transformation: The new pattern cannot be obtained by the above methods. If more than one method works, choose the one with the smallest index. Use exactly one of the above $7$ steps to accomplish this transformation.

The first line contains a positive integer $n$. Then follow $n$ lines, each containing $n$ characters, all `@` or `-`, representing the initial square. Then follow another $n$ lines, each containing $n$ characters, all `@` or `-`, representing the target square.

A single line containing a number between $1 \sim 7$ (as described above) indicating the transformation method required to convert the original square into the target square.

Constraints For $100\%$ of the testdata, $1 \le n \le 10$. Problem translation from NOCOW. USACO Training Section 1.2. Translated by ChatGPT 5