A1. Death Stars (easy)

Codeforces

IDCF958A1

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

The stardate is 1977 and the science and art of detecting Death Stars is in its infancy. Princess Heidi has received information about the stars in the nearby solar system from the Rebel spies and now, to help her identify the exact location of the Death Star, she needs to know whether this information is correct. Two rebel spies have provided her with the maps of the solar system. Each map is an _N_ × _N_ grid, where each cell is either occupied by a star or empty. To see whether the information is correct, Heidi needs to know whether the two maps are of the same solar system, or if possibly one of the spies is actually an Empire double agent, feeding her false information. Unfortunately, spies may have accidentally rotated a map by 90, 180, or 270 degrees, or flipped it along the vertical or the horizontal axis, before delivering it to Heidi. If Heidi can rotate or flip the maps so that two of them become identical, then those maps are of the same solar system. Otherwise, there are traitors in the Rebel ranks! Help Heidi find out. ## Input The first line of the input contains one number _N_ (1 ≤ _N_ ≤ 10) – the dimension of each map. Next _N_ lines each contain _N_ characters, depicting the first map: 'X' indicates a star, while 'O' indicates an empty quadrant of space. Next _N_ lines each contain _N_ characters, depicting the second map in the same format. ## Output The only line of output should contain the word _Yes_ if the maps are identical, or _No_ if it is impossible to match them by performing rotations and translations. [samples] ## Note In the first test, you can match the first map to the second map by first flipping the first map along the vertical axis, and then by rotating it 90 degrees clockwise.

星际历是1977年，探测死星的技术和艺术尚处于初级阶段。公主希迪从反抗军间谍处获得了附近星系中恒星的信息，现在，为了帮助她确定死星的确切位置，她需要知道这些信息是否正确。两名反抗军间谍向她提供了星系的两张地图。每张地图是一个 #cf_span[N × N] 的网格，每个单元格要么被恒星占据，要么为空。为了验证信息的正确性，希迪需要判断这两张地图是否描绘的是同一个星系，或者是否其中一名间谍实际上是帝国的双面间谍，向她提供虚假信息。不幸的是，间谍在将地图交付给希迪之前，可能不小心将地图旋转了90度、180度或270度，或者沿垂直轴或水平轴进行了翻转。如果希迪可以通过旋转或翻转地图，使其中两张变得完全相同，则说明这两张地图描绘的是同一个星系。否则，反抗军内部就有叛徒！请帮助希迪找出答案。输入的第一行包含一个数字 #cf_span[N]（#cf_span[1 ≤ N ≤ 10]）——每张地图的维度。接下来的 #cf_span[N] 行，每行包含 #cf_span[N] 个字符，描述第一张地图：'X' 表示恒星，'O' 表示太空中的空区域。接下来的 #cf_span[N] 行，每行包含 #cf_span[N] 个字符，以相同格式描述第二张地图。输出仅一行，如果两张地图可以通过旋转和翻转变得完全相同，则输出 _Yes_；否则输出 _No_。在第一个测试用例中，你可以通过先将第一张地图沿垂直轴翻转，然后顺时针旋转90度，使其与第二张地图匹配。 ## Input 输入的第一行包含一个数字 #cf_span[N]（#cf_span[1 ≤ N ≤ 10]）——每张地图的维度。接下来的 #cf_span[N] 行，每行包含 #cf_span[N] 个字符，描述第一张地图：'X' 表示恒星，'O' 表示太空中的空区域。接下来的 #cf_span[N] 行，每行包含 #cf_span[N] 个字符，以相同格式描述第二张地图。 ## Output 输出仅一行，如果两张地图可以通过旋转和翻转变得完全相同，则输出 _Yes_；否则输出 _No_。 [samples] ## Note 在第一个测试用例中，你可以通过先将第一张地图沿垂直轴翻转，然后顺时针旋转90度，使其与第二张地图匹配。

**Definitions** Let $ N \in \mathbb{Z} $, $ 1 \leq N \leq 10 $, be the dimension of two $ N \times N $ binary grids $ A $ and $ B $, where each cell is in $ \{ \text{X}, \text{O} \} $. Let $ \mathcal{G} $ be the group of transformations generated by: - Rotations by $ 90^\circ, 180^\circ, 270^\circ $, - Reflections along the vertical axis and horizontal axis. Let $ \mathcal{T}(A) = \{ g(A) \mid g \in \mathcal{G} \} $ denote the set of all distinct grids obtainable from $ A $ by applying any sequence of transformations in $ \mathcal{G} $. **Constraints** 1. $ A, B \in \{ \text{X}, \text{O} \}^{N \times N} $ 2. The transformations in $ \mathcal{G} $ are rigid (i.e., permutations of grid cells preserving adjacency structure). **Objective** Determine whether $ B \in \mathcal{T}(A) $. Output "Yes" if $ B $ is obtainable from $ A $ via some transformation in $ \mathcal{G} $; otherwise, output "No".

Samples

Input #1

4
XOOO
XXOO
OOOO
XXXX
XOOO
XOOO
XOXO
XOXX

Output #1

Yes

Input #2

2
XX
OO
XO
OX

Output #2

No

API Response (JSON)

{
  "problem": {
    "name": "A1. Death Stars (easy)",
    "description": {
      "content": "The stardate is 1977 and the science and art of detecting Death Stars is in its infancy. Princess Heidi has received information about the stars in the nearby solar system from the Rebel spies and now",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF958A1"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The stardate is 1977 and the science and art of detecting Death Stars is in its infancy. Princess Heidi has received information about the stars in the nearby solar system from the Rebel spies and now...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "星际历是1977年，探测死星的技术和艺术尚处于初级阶段。公主希迪从反抗军间谍处获得了附近星系中恒星的信息，现在，为了帮助她确定死星的确切位置，她需要知道这些信息是否正确。\n\n两名反抗军间谍向她提供了星系的两张地图。每张地图是一个 #cf_span[N × N] 的网格，每个单元格要么被恒星占据，要么为空。为了验证信息的正确性，希迪需要判断这两张地图是否描绘的是同一个星系，或者是否其中一名间谍实际上...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $, $ 1 \\leq N \\leq 10 $, be the dimension of two $ N \\times N $ binary grids $ A $ and $ B $, where each cell is in $ \\{ \\text{X}, \\text{O} \\} $.  \nLet $ \\math...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments