1.2.2 Transformations 方块转换

1.2.2 Transformations 方块转换

时间: 1ms        内存:64M

描述:

一块N x N(1<=N<=10)正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式: 1:转90度:图案按顺时针转90度。 2:转180度:图案按顺时针转180度。 3:转270度:图案按顺时针转270度。 4:反射:图案在水平方向翻转(以中央铅垂线为中心形成原图案的镜像)。 5:组合:图案在水平方向翻转,然后再按照1到3之间的一种再次转换。 6:不改变:原图案不改变。 7:无效转换:无法用以上方法得到新图案。 如果有多种可用的转换方法,请选择序号最小的那个。

输入:

第一行: 单独的一个整数N。 第二行到第N+1行: N行每行N个字符(不是“@”就是“-”);这是转换前的正方形。 第N+2行到第2*N+1行: N行每行N个字符(不是“@”就是“-”);这是转换后的正方形。

输出:

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

示例输入:

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

示例输出:

1

提示:

参考答案(内存最优[752]):

#include<stdio.h>
#include<string.h>
#define MAX 20
#define print(a) printf("%d\n",a)
void rese90(char str[][MAX],int n){
	int i,j;
	char temp[MAX][MAX]={0};
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			temp[j][n-1-i]=str[i][j];
	for(i=0;i<n;i++)
		strcpy(str[i],temp[i]);
}
void resei(char str[][MAX],int n)
{
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n/2;j++){
			char c=str[i][j];
			str[i][j]=str[i][n-1-j];
			str[i][n-1-j]=c;
		}
}
int judge(char str[][MAX],char order[][MAX],int n)
{
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(str[i][j]!=order[i][j])
				return 0;
	return 1;
}
int main()
{
	int n;
loop:	while(scanf("%d",&n)==1)
	{
		char str[MAX][MAX]={0},order[MAX][MAX]={0};
		int i,res=7;
		/*getchar();*/ 
		gets(str[0]);
		for(i=0;i<n;i++)
			gets(str[i]);
		for(i=0;i<n;i++)
			gets(order[i]);
		for(i=1;i<=3;i++){
			rese90(str,n);				
			if(judge(str,order,n)){
				res=i;
				print(res);
				goto loop;
			}					
		}
		rese90(str,n);
		resei(str,n);
		res=4;
		for(i=0;i<=3;i++){			
			if(judge(str,order,n)){
				print(res);
				goto loop;
			}
			rese90(str,n);	
			res=5;
		}
		resei(str,n);
		if(judge(str,order,n)){
			print(6);
			continue;
		}
		print(7);
	}
	return 0;
}

参考答案(时间最优[0]):


#include <iostream>
#include <fstream>
#include <string>
using namespace std;
char pre[11][11],now[11][11],temp[11][11],ch[11][11];
int n;
void method1(char ch[][11])
{
   for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      temp[i][j]=ch[n-j-1][i];
}
void method2(char ch[][11])
{
   for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
      temp[i][j]=ch[n-i-1][n-j-1];
}
void method3(char ch[][11])
{
   for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
      temp[i][j]=ch[j][n-i-1];

}
void method4(char ch[][11])
{
   for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
      temp[i][j]=ch[i][n-j-1];
}
bool IsSame(char ch1[][11],char ch2[][11])
{
  for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
       if(ch1[i][j]!=ch2[i][j])
        return false;
  return true;
}
int main() {
    ofstream fout ("transform.out");
    ifstream fin ("transform.in");
    cin>>n;
    for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
      cin>>pre[i][j];
    for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
      cin>>now[i][j];
    method1(pre);

    if(IsSame(temp,now))
   {
    cout<<"1";return 0;
   }
    else
    {
      method2(pre);
      if(IsSame(temp,now))
       {
        cout<<"2";return 0;
       }
      else
      {
       method3(pre);
       if(IsSame(temp,now))
       {
         cout<<"3";return 0;
       }
       else
       {
        method4(pre);
        if(IsSame(temp,now))
        {
          cout<<"4";return 0;
        }
        else
        {
         method4(pre);
         for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
             ch[i][j]=temp[i][j];
         method1(ch);
         if(IsSame(temp,now))
         {
          cout<<"5";return 0;
         }
         else
         {
            method4(pre);
           for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
             ch[i][j]=temp[i][j];
             method2(ch);
            if(IsSame(temp,now))
           {
            cout<<"5";return 0;
           }
            else
            {
              method4(pre);
              for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                 ch[i][j]=temp[i][j];
                 method3(ch);
              if(IsSame(temp,now))
             {
              cout<<"5";return 0;
             }
             else if(IsSame(pre,now))
             {
              cout<<"6";return 0;
             }
             else
             {
             cout<<"7";return 0;
             }
            }
         }
        }
       }
      }
    }
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注