1.2.2 USACO Transformations

末蓝、 2023-07-10 11:15 2阅读 0赞

**Transformations**

A square pattern of size N x N (1 <= N <= 10) black and white square tiles is transformed into another square pattern. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations:

*  \#1: 90 Degree Rotation: The pattern was rotated clockwise 90 degrees.
 *  \#2: 180 Degree Rotation: The pattern was rotated clockwise 180 degrees.
 *  \#3: 270 Degree Rotation: The pattern was rotated clockwise 270 degrees.
 *  \#4: Reflection: The pattern was reflected horizontally (turned into a mirror image of itself by reflecting around a vertical line in the middle of the image).
 *  \#5: Combination: The pattern was reflected horizontally and then subjected to one of the rotations (\#1-\#3).
 *  \#6: No Change: The original pattern was not changed.
 *  \#7: Invalid Transformation: The new pattern was not obtained by any of the above methods.

In the case that more than one transform could have been used, choose the one with the minimum number above.

### PROGRAM NAME: transform ###

### INPUT FORMAT ###

<table> 
 <tbody> 
  <tr> 
   <td>Line 1:</td> 
   <td>A single integer, N</td> 
  </tr> 
  <tr> 
   <td>Line 2..N+1:</td> 
   <td>N lines of N characters (each either `@' or `-'); this is the square before transformation</td> 
  </tr> 
  <tr> 
   <td>Line N+2..2*N+1:</td> 
   <td>N lines of N characters (each either `@' or `-'); this is the square after transformation</td> 
  </tr> 
 </tbody> 
</table>

### SAMPLE INPUT (file transform.in) ###

3
    @-@
    ---
    @@-
    @-@
    @--
    --@

### OUTPUT FORMAT ###

A single line containing the number from 1 through 7 (described above) that categorizes the transformation required to change from the \`before' representation to the \`after' representation.

### SAMPLE OUTPUT (file transform.out) ###

翻译：[https://www.luogu.com.cn/problem/P1205][https_www.luogu.com.cn_problem_P1205]

## 题目描述 ##

一块 n \\times nn×n 正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式：

*  转 90\\degree90°：图案按顺时针转 90\\degree90°。
 *  转 180\\degree180°：图案按顺时针转 180\\degree180°。
 *  转 270\\degree270°：图案按顺时针转 270\\degree270°。
 *  反射：图案在水平方向翻转（以中央铅垂线为中心形成原图案的镜像）。
 *  组合：图案在水平方向翻转，然后再按照 1 \\sim 31∼3 之间的一种再次转换。
 *  不改变：原图案不改变。
 *  无效转换：无法用以上方法得到新图案。

如果有多种可用的转换方法，请选择序号最小的那个。

只使用上述 77 个中的一个步骤来完成这次转换。

## 输入格式 ##

第一行一个正整数 nn。

然后 nn 行，每行 nn 个字符，全部为 `@` 或 `-`，表示初始的正方形。

接下来 nn 行，每行 nn 个字符，全部为 `@` 或 `-`，表示最终的正方形。

## 输出格式 ##

单独的一行包括 1 \\sim 71∼7 之间的一个数字（在上文已描述）表明需要将转换前的正方形变为转换后的正方形的转换方法。

## 输入输出样例 ##

**输入 \#1**复制

3
    @-@
    ---
    @@-
    @-@
    @--
    --@

**输出 \#1**复制

## 说明/提示 ##

【数据范围】  
对于 100\\%100% 的数据，1\\le n \\le 101≤n≤10。

题目翻译来自NOCOW。

USACO Training Section 1.2

> 思路1：枚举每一种翻转情况。求出每种翻转后的正确数组。

/*
    ID: L
    PROG: transform
    LANG: C++
    */
    #include<iostream>
    #include<cstdio>
    #define MAXM 13
    using namespace std;
    char a[MAXM][MAXM],b[MAXM][MAXM],c[MAXM][MAXM]; //a表示原始数组，b翻转后的最终数组，c镜面数组 
    bool fz1(int n,char a1[][MAXM],char b1[][MAXM])//90 
    {
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			if(a1[i][j] != b1[j][n+1-i]) return false;
    		}
    	}
    	return true;
    }
    bool fz2(int n, char a1[][MAXM], char b1[][MAXM])//180 
    {
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			if(a1[i][j] != b1[n+1-i][n+1-j]) return false;
    		}
    	}
    	return true;
    }
    bool fz3(int n, char a1[][MAXM], char b1[][MAXM])//270 
    {
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			if(a1[i][j] != b1[n+1-j][i]) return false;
    		}
    	}
    	return true;
    }
    bool fz4(int n,char a1[][MAXM], char b1[][MAXM])//镜面 
    {
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			if(a1[i][j] != b1[i][n+1-j]) return false;
    		}
    	}
    	return true;
    }
    
    bool fz6(int n, char a1[][MAXM], char b1[][MAXM])//不变 
    {
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			if(b1[i][j] != a1[i][j]) return false;
    		}
    	}
    	return true;
    }
    int main()
    {
    	freopen("transform.in","r",stdin);
    	freopen("transform.out","w",stdout);
    	int n;
    	cin >> n;
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			cin >> a[i][j];
    			c[i][n+1-j] = a[i][j];//镜面翻转后的数组 
    		}
    	}
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			cin >> b[i][j];
    		}
    	}
    	if(fz1(n,a,b))
    	{
    		cout << "1" << endl;
    		return 0;
    	}
    	if(fz2(n,a,b))
    	{
    		cout << "2" << endl;
    		return 0;
    	}
    	if(fz3(n,a,b))
    	{
    		cout << "3" << endl;
    		return 0;
    	}
    	if(fz4(n,a,b))
    	{
    		cout << "4" << endl;
    		return 0;
    	}
    	if(fz1(n,c,b) || fz2(n,c,b) || fz3(n,c,b))
    	{
    		cout << "5" << endl;
    		return 0;
    	}
    	if(fz6(n,a,b))
    	{
    		cout << "6" << endl;
    		return 0;
    	}
    	cout << "7" << endl;
    	fclose(stdin);
    	fclose(stdout);
    	return 0;
    }

> 思路2：虽然也是将每一种情况翻转后的结果枚举出来，但是枚举时可以找下规律，180度是90度翻转2次，270是90度翻转三次。

/*
    ID: Yan Liang
    PROG: transform
    LANG: C++
    */
    #include<iostream>
    #include<cstdio> 
    #define MAXM 13
    using namespace std;
    //b1表示翻转90度的结果，b2:180;b3:270;
    //b4代表水平翻转后再翻转90度的结果，b5:水平+180；b6：水平+270
    //c表示水平翻转后的结果 
    char a[MAXM][MAXM],b[MAXM][MAXM],c[MAXM][MAXM],b1[MAXM][MAXM],b2[MAXM][MAXM],b3[MAXM][MAXM]; 
    char b4[MAXM][MAXM],b5[MAXM][MAXM],b6[MAXM][MAXM];
    int n;
    void fz1(char a1[][MAXM],char b1[][MAXM])//翻转90度 
    {
    	for(int i = 1; i <= n; ++i)
    		for(int j = 1; j <= n; ++j)
    			b1[j][n+1-i] = a1[i][j];
    			
    		
    }
    bool check(char a1[][MAXM], char b1[][MAXM])//判断翻转后的数组和最终结果数组b是否相等 
    {
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			if(b1[i][j] != a1[i][j]) return false;
    		}
    	}
    	return true;
    }
    int main()
    {
    //	freopen("transform.in","r",stdin);
    	//freopen("transform.out","w",stdout);
    	cin >> n;
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			cin >> a[i][j];
    			c[i][n+1-j] = a[i][j];
    		}
    	}
    	for(int i = 1; i <= n; ++i)
    		for(int j = 1; j <= n; ++j)
    			cin >> b[i][j];
    	fz1(a,b1);fz1(b1,b2);fz1(b2,b3);fz1(c,b4);fz1(b4,b5);fz1(b5,b6);//180相当于90翻转两次 
    	if(check(b,b1)) cout << "1" << endl;
    	else if(check(b,b2)) cout << "2" << endl;
    	else if(check(b,b3)) cout << "3"  << endl;
    	else if(check(b,c)) cout << "4" << endl;
    	else if(check(b,b4) || check(b,b5)||check(b,b6)) cout << "5" << endl;
    	else if(check(a,b)) cout << "6" << endl;
    	else cout << "7" << endl;
    	return 0;
    }

> 代码可以进一步简化

/*
    ID: Yan Liang
    PROG: transform
    LANG: C++
    */
    #include<iostream>
    #include<cstdio> 
    #define MAXM 13
    using namespace std;
    char a[MAXM][MAXM],b[MAXM][MAXM],s[MAXM][MAXM];
    int n;
    void turn()
    {
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			b[i][j] = a[i][j];//保证多次翻转时都是再前一次的基础上翻转 
    		}
    	}
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			a[i][j] = b[n+1-j][i];//b翻转90度 
    		}
    	}
    }
    
    void turn2()
    {
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			b[i][j] = a[i][j];//保证b数组为原始数组，a翻转360度，已经还原了 
    		}
    	}
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			a[i][j] = b[i][n+1-j];//b镜面翻转后的结果得到a 
    		}
    	}
    }
    
    bool check()//判断翻转后的数组a和最终结果是否相等 
    {
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			if(a[i][j] != s[i][j]) return false;
    		}
    	}
    	return true;
    }
    int main()
    {
    //	freopen("transform.in","r",stdin);
    	//freopen("transform.out","w",stdout);
    	cin >> n;
    	for(int i = 1; i <= n; ++i)
    		for(int j = 1; j <= n; ++j)
    			cin >> a[i][j];
    	for(int i = 1; i <= n; ++i)
    		for(int j = 1; j <= n; ++j)
    			cin >> s[i][j];
    	turn();//翻转90度 
    	if(check()){
    		cout << "1" << endl; return 0;
    	 } 
    	turn();//翻转2次，180 
    	if(check()){
    		cout << "2" << endl; return 0;
    	}
    	turn();//270 
    	if(check()){
    		cout << "3" << endl; return 0;
    	} 
    	turn();//360度，a数组还原 
    	turn2();//镜面翻转 
    	if(check()){
    		cout << "4" << endl; return 0;
    	} 
    	turn(); 
    	if(check()){
    		cout << "5" << endl; return 0;
    	} 
    	turn();
    	if(check()){
    		cout << "5" << endl; return 0;
    	}
    	turn();
    	if(check()){
    		cout << "5" << endl; return 0;
    	} 
    	turn();
    	if(check()){
    		cout << "6" << endl; return 0;
    	}
    	cout << "7" << endl;
    	return 0;
    }

[https_www.luogu.com.cn_problem_P1205]: https://www.luogu.com.cn/problem/P1205