微软2015校招题 - 编程论坛

#2

rjsp2015-09-30 15:50

图像加密

想象一个正方形图像加密算法的步骤如下:
0.考虑图像为 N x N 矩阵
1.选择整数 k∈ {0，1，2，3}
2.顺时针方向旋转图像 k * 90 度
3.如果 N 是奇数则停止加密过程
4.如果 N 是偶数，则将图像分割成四个相等的子正方形，从步骤0开始递归加密

显然选择不同的 k 将导致不同的结果图像。
现在，给出两个图像 A 和 B，你的任务是判断B是否可能是从A加密而来的。

输入
输入的可能包含多个测试用例。
输入的第一行包含一个整数 T (1 < = T < = 10) 这是测试用例的数量。
每个测试用例的第一行是一个整数 N，表示图像 A 和 B 的边长。
以下 N 行，每行包含 N 的整数，表示 A 图像内容
接下来以下 N 行，表示 B 图像内容
1 <= N <= 100, 0 <= Aij, Bij <= 100000000

输出
如果B有可能是A加密而来，输出Yes，否则输出No

示例输入
Sample Input
3
2
12
34
31
42
2
12
43
31
42
4
4123
1234
2341
3412
3441
2312
1443
2132

示例输出
Yes
No
Yes

[ 本帖最后由 rjsp 于 2015-9-30 15:52 编辑 ]

#3

诸葛欧阳2015-09-30 16:19

好高级的样子

#4

yangfrancis2015-10-01 23:16

输入
输入的可能包含多个测试用例。
输入的第一行包含一个整数 T (1 < = T < = 10) 这是测试用例的数量。
每个测试用例的第一行是一个整数 N，表示图像 A 和 B 的边长。
以下 N 行，每行包含 N 的整数，表示 A 图像内容
接下来以下 N 行，表示 B 图像内容
1 <= N <= 100, 0 <= Aij, Bij <= 100000000

这个好难理解

#5

yangfrancis2015-10-01 23:22

好像有点看懂了……
慢慢研究吧，挺有意思的，真心希望此贴不沉。

#6

h11876477352015-10-04 11:45

顶起

#7

Susake2015-10-04 11:51

先mark

#8

the_second2015-10-06 11:19

如果图形A行数是偶数
它不断拆分，是每个正方形都要加密然后和B匹配吗

#9

yangfrancis2015-10-07 20:34

回复 8楼 the_second

我理解的是最初的Ａ和最后不需再加密之后的最终结果要匹配。

#10

wangfang12015-10-08 15:44

学习了

#11

诸葛欧阳2015-10-08 20:02

有人弄出来吗？

#12

yangfrancis2015-10-08 21:12

谈何容易，如果用递归的话，最后又怎么还原成一个大的矩阵，这是最蛋疼的。

#13

wmf20142015-10-09 10:12

从输入说明里没看到翻转系数k的输入。

#14

linan032015-10-10 11:49

k固定范围在代码里四种数值情况都要试过去来验证的吧。

那个示例输入没看明白，第一行是边长的话，为 3 ？

#15

yangfrancis2015-10-10 17:02

回复 14楼 linan03

那个3是输入的测试案例个数，以下三个案例连长分别是2,2,4

#16

yangfrancis2015-10-10 18:23

以下代码已经测试
#include<iostream>
#include<stdlib.h>
using namespace std;
class Matrix
{
public:
    char ** x;
    short width;
    Matrix(){x=0;
    };
    void Init(short w)
    {
        x = new char*[w];
        for(short i=0;i<w;i++)
           x[i]=new char[w];
        width=w;
    }
    friend bool operator==(Matrix mx1,Matrix mx2);
    friend bool operator!=(Matrix mx1,Matrix mx2);
};
bool operator==(Matrix mx1,Matrix mx2)
{
    short n;n=mx1.width;
    if(n!=mx2.width) return false;
    short row,col;
    for(row=0;row<n;row++)
    {
        for(col=0;col<n;col++)
            if(mx1.x[row][col]!=mx2.x[row][col])
                return false;
    }
    return true;
}
bool operator!=(Matrix mx1,Matrix mx2){return !(mx1==mx2);}
Matrix Roll90(Matrix mx)/*旋转90度*/
{
    short width;width=mx.width;
    Matrix temp;temp.Init(width);
    for(short row=0;row<width;row++)
    {
        for(short col=0;col<width;col++)
            temp.x[row][col]=mx.x[width-1-col][row];
    }
    return temp;
}
Matrix Roll180(Matrix mx)/*旋转180度*/
{
    short width;width=mx.width;
    Matrix temp;temp.Init(width);
    for(short row=0;row<width;row++)
    {
        for(short col=0;col<width;col++)
            temp.x[row][col]=mx.x[width-1-row][width-1-col];
    }
    return temp;
}
Matrix Roll270(Matrix mx)/*旋转270度*/
{
    short width;width=mx.width;
    Matrix temp;temp.Init(width);
    for(short row=0;row<width;row++)
    {
        for(short col=0;col<width;col++)
            temp.x[row][col]=mx.x[col][width-1-row];
    }
    return temp;
}
bool Split1(const Matrix mx,Matrix &submx)/*分裂出左上方的小矩阵*/
{
    short n;
    n=mx.width;
    if(n%2==1) return false;
    submx.Init(n/2);
    short row,col;
    for(row=0;row<submx.width;row++)
    {
        for(col=0;col<submx.width;col++)
        {
            submx.x[row][col]=mx.x[row][col];
        }
    }
    return true;
}
bool Split2(const Matrix mx,Matrix &submx)/*分裂出右上方的小矩阵*/
{
    short n;
    n=mx.width;
    if(n%2==1) return false;
    submx.Init(n/2);
    short row,col;
    for(row=0;row<submx.width;row++)
    {
        for(col=0;col<submx.width;col++)
        {
            submx.x[row][col]=mx.x[row][col+submx.width];
        }
    }
    return true;
}
bool Split3(const Matrix mx,Matrix &submx)/*分裂出左下方的小矩阵*/
{
    short n;
    n=mx.width;
    if(n%2==1) return false;
    submx.Init(n/2);
    short row,col;
    for(row=0;row<submx.width;row++)
    {
        for(col=0;col<submx.width;col++)
        {
            submx.x[row][col]=mx.x[row+submx.width][col];
        }
    }
    return true;
}
bool Split4(const Matrix mx,Matrix &submx)/*分裂出右下方的小矩阵*/
{
    short n;
    n=mx.width;
    if(n%2==1) return false;
    submx.Init(n/2);
    short row,col;
    for(row=0;row<submx.width;row++)
    {
        for(col=0;col<submx.width;col++)
        {
            submx.x[row][col]=mx.x[row+submx.width][col+submx.width];
        }
    }
    return true;
}
bool FillValue(Matrix &mx,char *str)//用字符串为矩阵赋值
{
    short size;
    size=mx.width*mx.width;
    if(size!=strlen(str)) return false;
    short row,col;
    for(row=0;row<mx.width;row++)
       for(col=0;col<mx.width;col++)
           mx.x[row][col]=str[row*mx.width+col];
    return true;
}
bool Compare(const Matrix mxSource,const Matrix mxTarget)
{
    if(mxSource.width!=mxTarget.width) return false;
    Matrix mxRolled;
    if(mxSource.width%2!=0)//不可再分割的情况
    {
        mxRolled=mxSource;//旋转0度
        if(mxRolled==mxTarget) return true;
        mxRolled=Roll90(mxSource);//旋转90度的情况
        if(mxRolled==mxTarget) return true;
        mxRolled=Roll180(mxSource);//旋转180度的情况
        if(mxRolled==mxTarget) return true;
        mxRolled=Roll270(mxSource);//旋转270度的情况
        if(mxRolled==mxTarget) return true;
        return false;//四种状况均不与目标方阵吻合
    }
    bool OK1=true,OK2=true,OK3=true,OK4=true;//用布尔变量记录四种转角递归后是否与目标区域一致
    Matrix submx1,submx2,submx3,submx4;
    Matrix subTg1,subTg2,subTg3,subTg4;
    Split1(mxTarget,subTg1);Split2(mxTarget,subTg2);Split3(mxTarget,subTg3);Split4(mxTarget,subTg4);
    /*获得目标矩形比较区域*/
    mxRolled=mxSource;//旋转0度
    Split1(mxRolled,submx1);Split2(mxRolled,submx2);Split3(mxRolled,submx3);Split4(mxRolled,submx4);
    /*获得源矩形比较区域*/
    if(!Compare(submx1,subTg1)) OK1=false;//左上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx2,subTg2)) OK1=false;//右上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx3,subTg3)) OK1=false;//左下角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx4,subTg4)) OK1=false;//右下角小方阵递归加密不与目标方阵相应区域吻合
    /*---------------------------------------------------------------------------------*/
    mxRolled=Roll90(mxSource);//旋转90度
    Split1(mxRolled,submx1);Split2(mxRolled,submx2);Split3(mxRolled,submx3);Split4(mxRolled,submx4);
    /*获得源矩形比较区域*/
    if(!Compare(submx1,subTg1)) OK2=false;//左上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx2,subTg2)) OK2=false;//右上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx3,subTg3)) OK2=false;//左下角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx4,subTg4)) OK2=false;//右下角小方阵递归加密不与目标方阵相应区域吻合
    /*---------------------------------------------------------------------------------*/
    mxRolled=Roll180(mxSource);//旋转180度
    Split1(mxRolled,submx1);Split2(mxRolled,submx2);Split3(mxRolled,submx3);Split4(mxRolled,submx4);
    /*获得源矩形比较区域*/
    if(!Compare(submx1,subTg1)) OK3=false;//左上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx2,subTg2)) OK3=false;//右上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx3,subTg3)) OK3=false;//左下角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx4,subTg4)) OK3=false;//右下角小方阵递归加密不与目标方阵相应区域吻合
    /*---------------------------------------------------------------------------------*/
    mxRolled=Roll270(mxSource);//旋转270度
    Split1(mxRolled,submx1);Split2(mxRolled,submx2);Split3(mxRolled,submx3);Split4(mxRolled,submx4);
    /*获得源矩形比较区域*/
    if(!Compare(submx1,subTg1)) OK4=false;//左上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx2,subTg2)) OK4=false;//右上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx3,subTg3)) OK4=false;//左下角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx4,subTg4)) OK4=false;//右下角小方阵递归加密不与目标方阵相应区域吻合
    if(OK1||OK2||OK3||OK4)
       return true;
    else
       return false;
}
int main()
{
    Matrix A,B;
    short number;/*测试次数*/short w;/*边长变量*/
    char str1[101],str2[101];/*为源矩阵和目标矩阵赋值的字符串*/
    cout<<"请输入想要测试的次数：";
    cin>>number;
    short row,col;//用于循环遍历赋值
    for(short i=0;i<number;i++)
    {
        cout<<"请输入边长：";
        cin>>w;A.Init(w);B.Init(w);
        cout<<"请输入含"<<w*w<<"个字符的字符串，为源矩阵赋值：";
        cin>>str1;
        cout<<"请输入含"<<w*w<<"个字符的字符串，为目标矩阵赋值：";
        cin>>str2;
        if(!FillValue(A,str1)){cout<<"非法输入，按任意键退出。\n";system("pause");return 0;}
        if(!FillValue(B,str2)){cout<<"非法输入，按任意键退出。\n";system("pause");return 0;}
        for(row=0;row<w;row++)
        {
           for(col=0;col<w;col++)
              cout<<'\t'<<A.x[row][col];
           cout<<endl;
        }
        cout<<endl;
        for(row=0;row<w;row++)
        {
           for(col=0;col<w;col++)
              cout<<'\t'<<B.x[row][col];
           cout<<endl;
        }
        if(Compare(A,B)) cout<<"YES!";
        else cout<<"NO!";
    }
    system("pause");
    return 0;
}

#17

azzbcc2016-11-17 14:40

练练手，果然c++忘的差不多了，查资料就用了不少时间。

程序代码：

#include <vector>
#include <fstream>
#include <iostream>

using namespace std;
typedef vector<unsigned> linear_array;
typedef vector<linear_array> dyadic_array;

class Matrix {
private:
    char flag;
    dyadic_array data;
    size_t length, angle;

    void rotate90(size_t x_pos, size_t y_pos, size_t range);

    void rotate(size_t range, size_t x_pos, size_t y_pos);

public:
    Matrix(size_t length, char flag) : length(length), flag(flag), angle(0) {}

    void rotate();

    bool operator ==(const Matrix &matrix) const;

    friend istream &operator >>(istream &is, Matrix &matrix);

    friend ostream &operator <<(ostream &os, const Matrix &matrix);
};

void Matrix::rotate90(size_t x_pos, size_t y_pos, size_t range) {
    dyadic_array array(range, linear_array(range));
    for (size_t x = 0; x != range; ++x) {
        for (size_t y = 0; y != range; ++y) {
            array[x][y] = this->data[x_pos + range - 1 - y][y_pos + x];
        }
    }
    for (size_t x = 0; x != array.size(); ++x) {
        for (size_t y = 0; y != array[x].size(); ++y) {
            this->data[x_pos + x][y_pos + y] = array[x][y];
        }
    }
}

void Matrix::rotate(size_t range, size_t x_pos, size_t y_pos) {
    rotate90(x_pos, y_pos, range);

    if (range % 2 || range <= 2) return;
    size_t length = range / 2;

    rotate(length, x_pos, y_pos);
    rotate(length, x_pos, y_pos + length);
    rotate(length, x_pos + length, y_pos);
    rotate(length, x_pos + length, y_pos + length);
}

void Matrix::rotate() {
    this->angle += 90;
    rotate(this->length, 0, 0);
}

bool Matrix::operator ==(const Matrix &matrix) const {
    return this->length == matrix.length && this->data == matrix.data;
}

istream &operator >>(istream &is, Matrix &matrix) {
    for (size_t i = 0; i != matrix.length; ++i) {
        matrix.data.push_back(linear_array(matrix.length));
        for (size_t j = 0; j != matrix.length; ++j) {
            is >> matrix.data[i][j];
        }
    }
    return is;
}

ostream &operator <<(ostream &os, const Matrix &matrix) {
    os << "Matrix(" << matrix.flag << ", " << matrix.angle << ") :" << endl;
    for (size_t i = 0; i != matrix.length; ++i) {
        for (size_t j = 0; j != matrix.length; ++j) {
            os << matrix.data[i][j] << ' ';
        }
        os << endl;
    }
    return os;
}

int main(void) {
    bool flag;
    size_t T, N;

    ifstream in("stdin");
    if (in.fail()) return -1;

    in >> T;
    while (T--) {
        in >> N;

        Matrix A(N, 'A'), B(N, 'B');
        in >> A >> B;

        flag = A == B;
        for (int i = 0; i < 3; ++i) {
            A.rotate();
            if (A == B) flag = true;
        }

        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    in.close();

    return 0;
}

[此贴子已经被作者于2016-11-17 14:45编辑过]