P1205 [USACO1.2]方块转换 Transformations

标签 搜索/枚举 USACO

题目描述

一块N x N（1<=N<=10）正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式：

1：转90度：图案按顺时针转90度。

2：转180度：图案按顺时针转180度。

3：转270度：图案按顺时针转270度。

4：反射：图案在水平方向翻转（以*铅垂线为中心形成原图案的镜像）。

5：组合：图案在水平方向翻转，然后再按照1到3之间的一种再次转换。

6：不改变：原图案不改变。

7：无效转换：无法用以上方法得到新图案。

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

只使用1–7中的一个步骤来完成这次转换。

输入输出格式

输入格式：

第一行： 单独的一个整数N。

第二行到第N+1行： N行每行N个字符（不是“@”就是“-”）；这是转换前的正方形。

第N+2行到第2*N+1行： N行每行N个字符（不是“@”就是“-”）；这是转换后的正方形。

输出格式：

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

输入输出样例

输入样例#1：

3

@-@

@@-

@-@

@–

–@

输出样例#1：

1

说明

题目翻译来自NOCOW。

USACO Training Section 1.2

#include<iostream>

#include<cstdio>

#define MAXN 11

#define R for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)

using namespace std;

int tot=7,n;

char g[MAXN][MAXN],s[MAXN][MAXN],tmp[MAXN][MAXN],w[MAXN][MAXN];

int read(){

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();

    return x*f;

}

void init(){

    n=read();

    for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++)

     cin>>s[i][j],w[i][j]=s[i][j];

    for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++)

     cin>>g[i][j];

}

bool jd(){

    for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++)

     if(w[i][j]!=g[i][j]) return false;

    return true;

}

void z90(){

    for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++)

    tmp[j][n-i+1]=w[i][j];

    for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++)

      w[i][j]=tmp[i][j];

}

void xz(){

    R w[i][j]=s[i][n-j+1];

}

void slove(){

    if(jd()) tot=min(6,tot);

    z90(); if(jd()) tot=min(1,tot);

    z90(); if(jd()) tot=min(2,tot);

    z90(); if(jd()) tot=min(3,tot);

    xz();  if(jd()) tot=min(4,tot);

    for(int i=1;i<=3;i++){

        z90();if(jd()) tot=min(5,tot);

    }

    printf("%d",tot);

}

int main(){

    init();

    slove();

    return 0;

}