一、题目大意

题目链接：https://atcoder.jp/contests/abc218/tasks/abc218_c

Problem Statement

We have two figures SS and TT on a two-dimensional grid with square cells.

SS lies within a grid with NN rows and NN columns, and consists of the cells where S_{i,j}Si,j​ is #.
TT lies within the same grid with NN rows and NN columns, and consists of the cells where T_{i,j}Ti,j​ is #.

Determine whether it is possible to exactly match SS and TT by 9090-degree rotations and translations.

Constraints

• 1 \leq N \leq 2001≤N≤200
• Each of SS and TT consists of # and ..
• Each of SS and TT contains at least one #.

---

Input

Input is given from Standard Input in the following format:

NN
S_{1,1}S_{1,2}\ldots S_{1,N}S1,1​S1,2​…S1,N​
\vdots⋮
S_{N,1}S_{N,2}\ldots S_{N,N}SN,1​SN,2​…SN,N​
T_{1,1}T_{1,2}\ldots T_{1,N}T1,1​T1,2​…T1,N​
\vdots⋮
T_{N,1}T_{N,2}\ldots T_{N,N}TN,1​TN,2​…TN,N​

Output

Print Yes if it is possible to exactly match SS and TT by 9090-degree rotations and translations, and No otherwise.

---

Sample Input 1 Copy

Copy

5
.....
..#..
.###.
.....
.....
.....
.....
....#
...##
....#

Sample Output 1 Copy

Copy

Yes

We can match SS to TT by rotating it 9090-degrees counter-clockwise and translating it.

---

Sample Input 2 Copy

Copy

5
#####
##..#
#..##
#####
.....
#####
#..##
##..#
#####
.....

Sample Output 2 Copy

Copy

No

It is impossible to match them by 9090-degree rotations and translations.

---

Sample Input 3 Copy

Copy

4
#...
..#.
..#.
....
#...
#...
..#.
....

Sample Output 3 Copy

Copy

Yes

Each of SS and TT may not be connected.

---

Sample Input 4 Copy

Copy

4
#...
.##.
..#.
....
##..
#...
..#.
....

Sample Output 4 Copy

Copy

No

Note that it is not allowed to rotate or translate just a part of a figure; it is only allowed to rotate or translate a whole figure.

大意就是给两个矩阵，看里面的'#'能否通过旋转、平移重合

二、ac代码

#include<bits/stdc++.h>
using namespace std;

struct node{
int x,y;
};
map<int,node>mp;
bool comp(const node &a,const node &b)
{
    if (a.x==b.x) return a.y<b.y;
    else return a.x<b.x;
}
int main(void)
{
    string s;
    vector<node>vec;
    ios::sync_with_stdio(0);
    int n,cnt=0,flag=1;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>s;
        for (int j=0;j<n;j++)
        {
            if (s[j]=='#')
            {
                node t;
                t.x=i,t.y=j+1;
                mp[cnt++]=t;  //序号与坐标
            }
        }
    }
    for (int i=1;i<=n;i++)
    {
        cin>>s;
        for (int j=0;j<n;j++)
        {
            if (s[j]=='#')
            {
                node t;
                t.x=i,t.y=j+1;
                vec.push_back(t);
            }
        }
    }
    if (cnt!=vec.size())  //个数不相等，肯定不可能重合
    {
        cout<<"No";
        return 0;
    }
    for (int i=1;i<=4;i++)
    {
        flag=1;
        for (int j=0;j<vec.size();j++)  //更新旋转后的坐标
        {
            swap(vec[j].x,vec[j].y);
            vec[j].y=n-vec[j].y+1;
        }
        sort(vec.begin(),vec.end(),comp);  //按照从左到右，从上到下的顺序排序
        int row=vec[0].x-mp[0].x; //判断旋转后的第一个坐标和要比较的第一个坐标的行的关系
        int column=vec[0].y-mp[0].y; //判断旋转后的第一个坐标和要比较的第一个坐标的列的关系
        for (int j=1;j<cnt;j++)
        {
            if (mp[j].x+row==vec[j].x&&mp[j].y+column==vec[j].y) continue;
            else
            {
                flag=0;
                break;
            }
        }
        if (flag) break;
    }
    if (flag) cout<<"Yes";
    else cout<<"No";
    return 0;
}

思路就是每次将第二个矩阵旋转90°，依次判断每个点的距离是不是完全一样

 

.....
..#..
.###.
.....
.....
.....
.....
....#
...##
....#

以这个样例为例，如果能旋转平移重合的话，每个点相对应的关系是一样的，类似相似三角形

..#..
.###.
.....
.....
.....
.....
.....
.....
.#...
###..
因此，在开始的map中已经保存好了上面矩阵的信息，下面的矩阵每次旋转完sort排序，得到的就是从左到右从上到下依次的点

 

 

 

peace