AtCoder Beginner Contest 218 C - Shapes (模拟)

linkkkk
题意：
给两个 n ∗ n n*n n∗n的矩阵， # \# #表示物体所在位置，问 1 1 1能否通过旋转 90 ° 90° 90°和平移任意次得到 2 2 2
思路：
啊大概就是暴力模拟判断一下，然后就没想好怎么模拟。
首先，如果两个矩阵的#个数不相等，一定是 N o No No
然后，旋转 90 ° 90° 90°任意次，其实只需要旋转 4 4 4次就足够了。
平移的话，对于每次旋转后的图形，找到最左上的起点，然后判断其他点和这个点问位置关系。
代码：

int n;
int s[210][210],t[210][210];
int cnts=0,cntt=0;
string ss;
int a[210][210];

void cul(){
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            a[n-i-1][j]=t[j][i];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            t[i][j]=a[i][j];
}

PII Find(int s[210][210]){
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
    if(s[i][j]) return {i,j};
}

int main(){
    n=read;
    rep(i,0,n-1){
        cin>>ss;
        for(int j=0;j<ss.size();j++)
            if(ss[j]=='#'){
                cnts++;
                s[i][j]=1;
            }
    }
    rep(i,0,n-1){
        cin>>ss;
        for(int j=0;j<ss.size();j++)
            if(ss[j]=='#'){
                cntt++;
                t[i][j]=1;
            }
    }
    if(cnts!=cntt){
        puts("No");return 0;
    }
    for(int k=1;k<=4;k++){
        cul();
        PII first_s=Find(s);
        PII first_t=Find(t);
        int xa=first_s.first,ya=first_s.second;
        int xb=first_t.first,yb=first_t.second;
        int xc=xb-xa,yc=yb-ya;
        bool flag=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                if(s[i][j]==1){
                    int nx=i+xc,ny=j+yc;
                    if(nx<0||nx>=n||ny<0||ny>=n){
                        flag=0;break;
                    }
                    else{
                        if(!t[nx][ny]){
                            flag=0;break;
                        }
                    }
                }
            if(!flag) break;
        }
        if(flag){
            puts("Yes");return 0;
        }
    }
    puts("No");

    return 0;
}
/*


*/