hiho一下第114周《Image Encryption》题目分析

10
3

题目大意

给定一个长宽均为N的矩阵,可以对矩阵进行如下操作:

  1. N为偶数,则可以将原矩阵分割为4个长宽N/2子矩阵,并且分别对4个子矩阵进行同样的操作
  2. 将该矩阵顺时针旋转90°,180°,或270°,也可以选择不旋转

题目中有对旋转操作更详细的说明,这里不再赘述。

现在给定一对矩阵,问其中一个能否通过上述操作变换至另一个矩阵。

解题思路

首先需要发现一点:"变换成"实际上是一个等价关系,A->B(A能旋转到B)意味着B->A,A->B->C意味着A->C。题目的要求就是给定两个矩阵,判断它们是不是等价的。解决这类等价问题的一个常用方法是"最小表示法"。

我们来看一个简单的"最小表示法"的例子:

给定两个长度相等的字符串S1和S2,判断是否可以通过"若干次交换S1中任意两个字符"使得S1->S2。

容易看出这里的变换规则也是一种等价关系。我们不太容易直接判断S1和S2是否等价,但是能够容易判断出S1能变换到的"字典序最小"的字符串是什么(只需要将S1的字符排序即可)。例如232112能够变成的最小字符串是112223321221能够变换成的最小字符串也是112223,所以我们判断出132112321221等价。


所以本题的解决思路也是一样:对于给定的两个数字矩阵,我们均计算出其最小表示,检查两个矩阵的最小表示是否相等。

首先我们需要去定义在数字矩阵中的最小字典序含义。

这里给出一个定义:对于两个数字矩阵A,B,我们从上至下、从左至右逐个元素比较。若存在一个A(i,j)<B(i,j),则我们认为A<B

例如下面两个例子,右边的数字矩阵就为左边矩阵的最小表示:

3 1         1 4
2 4  ====>  3 2

3 1 3 2         1 2 1 2
2 4 1 4         4 3 3 4
2 4 1 2  ====>  1 3 1 4
1 3 4 3         4 2 3 2

接下来考虑如何求解最小表示。

由于题目中可以队切割后的子矩阵进行同样的变换,因此考虑迭代完成。

先将矩阵分割为最小的单元,再逐步往上回溯,其伪代码为:

dfs(matrix, n):
    If (n is odd) Then
        // matrix为最小单元
        // 直接旋转当前矩阵,获取最小表示
        min = matrix
        tp = matrix
        For i = 1 .. 3  // 旋转3次
            tp = rotate(tp) // 旋转矩阵
            If (min > tp) Then
                // 比较字典序
                min = tp
            End If
        End For
        matrix = min
    Else
        // matrix可以分割
        // 继续切割,先处理子矩阵
        dfs(sub_matrix_top_left, n / 2)
        dfs(sub_matrix_top_right, n / 2)
        dfs(sub_matrix_bottom_left, n / 2)
        dfs(sub_matrix_bottom_right, n / 2)
        // 到这一步时,原矩阵的4个子矩阵均为最小表示
        // 此时的旋转,我们采用以块为单位旋转
        min = matrix
        tp = matrix
        For i = 1 .. 3  // 旋转3次
            tp = rotate_matrix(tp) // 旋转矩阵
            If (min > tp) Then
                // 比较字典序
                min = tp
            End If
        End For
        matrix = min
    End If

在上面的代码中rotate()函数即为简单的旋转操作。

rotate_matrix()的为块的旋转操作,其思想为将原矩阵分割为4块,进行swap而不改变子矩阵的方向:

         A(1) | A(2)
matrix = -----------
         A(4) | A(3)

则执行rotate_matrix(matrix)变换后为:

         A(4) | A(1)
matrix = -----------
         A(3) | A(2)

举个例子:

 1  2  3  4         9 10  1  2
 5  6  7  8   =>   13 14  5  6
 9 10 11 12        11 12  3  4
 13 14 15 16        15 16  7  8

所以rotate_matrix的操作更像是:

rotate_matrix():
    swap(top_left, top_right)
    swap(top_right, bottom_right)
    swap(bottom_right, bottom_left)

这样做的目的是为了保证每个不能分割的单元其方向不再改变。

由于本题中N的数据范围不大,因此直接采用寻找最小表示的算法也能够顺利通过所有的测试数据。

5 answer(s)

0

请问n为奇数时如何旋转

  • 比如n=5,依次填1..25

  • n为奇数时不能分割,所以只能把整个矩阵旋转90° 180° 270°

  • 添加评论
  • reply
0

写了个省点空间,不用另开空间新存矩阵的,用一个整数存取变换,然后变换坐标到原矩阵去取数就行了,最后跑下来6M内存。

#include<cstdio>
#include<cstring>
#include<cstdlib>
int n,m;
int A[110][110],B[110][110];
int * translate(int s,int t,int N,int type){
    int * ans=new int[2];
    int i=s/N;
    int j=t/N;
    s=s%N;
    t=t%N;
    i*=N;
    j*=N;

    if (type==0){
        ans[0]=i+s;
        ans[1]=j+t;
    }
    else if (type==1){
        ans[0]=i+N-t-1;
        ans[1]=j+s;
    }
    else if (type==2){
        ans[0]=i+N-s-1;
        ans[1]=j+N-t-1;
    }
    else if (type==3){
        ans[0]=i+t;
        ans[1]=j+N-s-1;
    }
    return ans;
    //对点s,t进行变换
}

bool test(int s,int t,int N,int rot){

    //rot为一个状态压缩的数值,储存变换
    for (int k=0;k<4;k++){
        //printf("\n");
        bool conti=true;
        for (int i=0;i<N;i++){
            if (!conti) break;
            for (int j=0;j<N;j++){
                int rotation=rot;
                int * trans=translate(s+i,t+j,N,k);
                int x=trans[0];
                int y=trans[1];
                delete [] trans;
                int n=N*2;
                while (rotation){
                    int type=rotation%4;
                    trans=translate(x,y,n,type);
                    n*=2;
                    x=trans[0];
                    y=trans[1];
                    delete [] trans;
                    rotation=rotation>>2;
                }

                //根据rot对点进行变换

                //printf("%d %d %d %d %d %d\n",s+i,t+j,x,y,A[s+i][t+j],B[x][y]);
                if (A[s+i][t+j]!=B[x][y]) {
                    conti=false;
                    break;
                }
            }
        }
        if (conti) return true;
    }

    return false;
}

bool solve(int s,int t,int N,int rot){
    //深搜
    if ((N&1) || N<=2){
        return test(s,t,N,rot);
    }

    int M=N>>1;
    //bool res=false;

    for (int i=0;i<4;i++){
        if (!solve(s,t,M,(rot<<2)+i)) continue;
        if (!solve(s+M,t,M,(rot<<2)+i)) continue;
        if (!solve(s,t+M,M,(rot<<2)+i)) continue;
        if (!solve(s+M,t+M,M,(rot<<2)+i)) continue;
        else return true;
    }
    //枚举4个可能的角度
    return false;
}

int main(){
    freopen("hw114.in","r",stdin);

    scanf("%d",&n);
    int t;
    for (int i=0;i<n;i++){
        scanf("%d",&t);
        for (int j=0;j<t;j++)
            for (int k=0;k<t;k++)
                scanf("%d",&A[j][k]);
        for (int j=0;j<t;j++)
            for (int k=0;k<t;k++)
                scanf("%d",&B[j][k]);

        if (solve(0,0,t,0)){
            printf("Yes\n");
        }
        else printf("No\n");
    }
}
  • 我是新手,我想问一下如何提交c++代码?在编辑框里没有看到c++这个选项

  • 添加评论
  • reply
0

dfs里面反复调用rotate_matrix会不会导致程序很慢?这个程序要对A和B分别求最小表示,不知道题主的程序测试用时是多少?

0
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int t, n;


struct point{
    int x, y;
    point(int x, int y){
        this->x = x;
        this->y = y;
    }
};

void myswap(vector< vector<int> >& res, point p1, point p2, int N){
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            swap(res[i+p1.x][j+p1.y], res[i+p2.x][j+p2.y]);
}

vector< vector<int> >& rotate_mat(vector< vector<int> >& res, int N){
    // vector< vector<int> > ret(N, vector<int>(N, 0));
    myswap(res, point(0, 0), point(0, N), N);
    myswap(res, point(0, 0), point(N, 0), N);
    myswap(res, point(N, 0), point(N, N), N);
    return res;
}

vector< vector<int> > rotate(vector< vector<int> >& res, int N){
    vector< vector<int> > ret(N, vector<int>(N, 0));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            ret[j][N-i-1] = res[i][j];
        }
    }
    return ret;
}

bool comp(vector< vector<int> >& f, vector< vector<int> >& t, int N){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(f[i][j]<t[i][j])
                return true;
            else if(f[i][j]>t[i][j])
                return false;
        }
    }
    return false;
}


void dfs(vector< vector<int> >& res, int N, int i, int j){
    if(N%2==0){
        dfs(res, N/2, 0, 0);
        dfs(res, N/2, 0, N/2);
        dfs(res, N/2, N/2, 0);
        dfs(res, N/2, N/2, N/2);
    }
    vector< vector<int> > min(N, vector<int>(N, 0));
    vector< vector<int> > tp(N, vector<int>(N, 0));
    for(int row=i;row<i+N;row++)
        for(int col=j;col<j+N;col++){
            min[row-i][col-j] = res[row][col];
            tp[row-i][col-j] = res[row][col];
        }
    for(int k=0;k<3;k++){
        if(N%2==0)
            tp = rotate_mat(tp, N/2);
        else
            tp = rotate(tp, N);
        if(comp(tp, min, N))
            min = tp;
    }
    for(int row=i;row<i+N;row++)
        for(int col=j;col<j+N;col++)
            res[row][col] = min[row-i][col-j];
}




int main(){
    while(cin>>t){
        while(t--){
            cin>>n;
            vector< vector<int> > A(n, vector<int>(n, 0)), B(n, vector<int>(n, 0));
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    cin>>A[i][j];
                }
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    cin>>B[i][j];
                }
            }
            // cout<<"->>>>>>>>1"<<endl;
            dfs(A, n, 0, 0);
            dfs(B, n, 0, 0);
            // cout<<"->>>>>>>>2"<<endl;
            int i, j;
            for(i=0;i<n;i++){
                for(j=0;j<n;j++){
                    if(A[i][j]!=B[i][j]){
                        cout<<"No"<<endl;
                        break;
                    }
                }
                if(j!=n)
                    break;
            }
            if(i==n)
                cout<<"Yes"<<endl;
        }
    }
}

您好,按照您上面的思路,我自己写了一个比较繁琐的代码,但是WA了,请问是什么问题?

  • 貌似你的comp函数写的有问题!!

  • 我用的答主的comp函数AC了= =

  • 那么请问comp函数应该如何写呢?

  • 哥们,找到怎么错了吗

  • 添加评论
  • reply
0

你好,请问你上面列举的字符串最小表示是否写错了? 以及rotate_matrix的问题,是否应该是: rotate_matrix(): swap(top_left, top_right) swap(top_left, bottom_left) swap(bottom_right, bottom_left)

请指教,谢谢~

  • 如果按照你的rotate方法,会从[1,2;3,4]变成[3,1;4,2]

  • 难道不是这样子的吗?

  • 对的,应该就是这样。

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享