微软笔试题 《Image Encryption》

题目1 : Image Encryption

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 A fancy square image encryption algorithm works as follow:

0. consider the image as an N x N matrix

1. choose an integer k∈ {0, 1, 2, 3}

2. rotate the square image k * 90 degree clockwise

3. if N is odd stop the encryption process

4. if N is even split the image into four equal sub-squares whose length is N / 2 and encrypt them recursively starting from step 0

Apparently different choices of the k serie result in different encrypted images. Given two images A and B, your task is to find out whether it is POSSIBLE that B is encrypted from A. B is possibly encrypted from A if there is a choice of k serie that encrypt A into B.

输入 Input may contains multiple testcases.

The first line of the input contains an integer T(1 <= T <= 10) which is the number of testcases.

The first line of each testcase is an integer N, the length of the side of the images A and B.

The following N lines each contain N integers, indicating the image A.

The next following N lines each contain N integers, indicating the image B.

For 20% of the data, 1 <= n <= 15

For 100% of the data, 1 <= n <= 100, 0 <= Aij, Bij <= 100000000

输出 For each testcase output Yes or No according to whether it is possible that B is encrypted from A.

样例输入

3
2
1 2
3 4
3 1
4 2
2
1 2
4 3
3 1
4 2
4
4 1 2 3
1 2 3 4
2 3 4 1
3 4 1 2
3 4 4 1
2 3 1 2
1 4 4 3
2 1 3 2

样例输出

Yes
No
Yes

以下是个人做题代码*********

时间：6s左右 内存：32M

import java.util.Scanner;

public class ImageEncryption {

	/**
	 *@author z.wantong
	 *@param args
	 *@since 2016-9-6 上午9:45:28
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		int nTestCase = in.nextInt();
		for(int i=1; i<=nTestCase; i++){
			int nDemension = in.nextInt();
			int A[][] = new int[nDemension][nDemension];
			int B[][] = new int[nDemension][nDemension];
			for(int j=0;j<nDemension;j++){
				for(int k=0; k<nDemension; k++){
					A[j][k] = in.nextInt();
				}
			}
			for(int j=0;j<nDemension;j++){
				for(int k=0; k<nDemension; k++){
					B[j][k] = in.nextInt();
				}
			}
			boolean result = checkEncryption(A, B , nDemension);
			if(result) System.out.println("Yes");
			else System.out.println("No");
		}
	}
	public static boolean checkEncryption(int A[][], int B[][] ,int N){
		
		int temp[][] = new int[N][N];
		for(int i=0; i<N; i++){
			System.arraycopy(A[i], 0, temp[i], 0, N);
		}
		//0度
		if(checkEquals(temp, B, 0, 0, N)) return true;
		else{
			if(subCheck(temp, B, N))return true;
		}
		temp = rotate(A, 1);
		if(checkEquals(temp, B, 0, 0, N)) return true;
		else{
			if(subCheck(temp, B, N))return true;
		}
		temp = rotate(A, 2);
		if(checkEquals(temp, B, 0, 0, N)) return true;
		else{
			if(subCheck(temp, B, N))return true;
		}
		temp = rotate(A, 3);
		if(checkEquals(temp, B, 0, 0, N)) return true;
		else{
			if(subCheck(temp, B, N))return true;
		}
		
		return false;
	}
	public static int[][] rotate(int source[][] , int k){
		
		int N = source.length;
		int result[][] = new int[N][N];
		if(N<2) {
			result[0][0]=source[0][0];
			return result;
		}
		double centerX = (N-1)/2.0;
		double centerY = (N-1)/2.0;
		for(int i=0; i<N; i++)
			for(int j=0; j<N; j++){
				int x0 = (int) Math.round((i-centerX)*Math.cos(k* Math.PI/2) + (j-centerY)*Math.sin(k*Math.PI/2) +centerX);
				int y0 = (int) Math.round((j-centerY)*Math.cos(k*Math.PI/2) - (i-centerX)*Math.sin(k* Math.PI/2)+centerY);
				result[x0][y0] = source[i][j];
			}
		
		return result;
	}
	
	public static boolean checkEquals(int A[][], int B[][], int starti, int startj, int n){
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++){
				if(A[i][j]!=B[i][j]) return false;
			}
		return true;
	}
	public static boolean subCheck(int A[][], int B[][], int N){
		boolean res = false;
		if(N%2 == 0){
			int subA[][] = new int[N/2][N/2];
			int subB[][] = new int[N/2][N/2];
			for(int i=0; i<N/2;i++)
				for(int j=0; j<N/2; j++){
					subA[i][j]=A[i][j];
					subB[i][j]=B[i][j];
				}
			res = checkEncryption(subA, subB, N/2);
			if(res){
				for(int i=0; i<N/2;i++)
					for(int j=0; j<N/2; j++){
						subA[i][j]=A[i][j+N/2];
						subB[i][j]=B[i][j+N/2];
					}
				res = checkEncryption(subA, subB, N/2);
			}
			if(res){
				for(int i=0; i<N/2;i++)
					for(int j=0; j<N/2; j++){
						subA[i][j]=A[i+N/2][j];
						subB[i][j]=B[i+N/2][j];
					}
				res = checkEncryption(subA, subB, N/2);
			}
			if(res){
				for(int i=0; i<N/2;i++)
					for(int j=0; j<N/2; j++){
						subA[i][j]=A[i+N/2][j+N/2];
						subB[i][j]=B[i+N/2][j+N/2];
					}
				res = checkEncryption(subA, subB, N/2);
			}
			
		}
		return res;
	}
}