Resolução de problemas/Cubos coloridos

O problema

O problema requer a elaboração de um programa que recebe como entrada as faces dos cubos, e gera como saida a quantidade de cubos iguais para cada caso de teste.

Como resolver

A entrada

Neste programa, as cores dos cubos são representadas por números. A ordem em que as cores são colocadas na entrada são descritas no problema. Admito que 0,1,2,3,4,5 correspondem as posições em que as cores são inseridas. No exemplo da questão a entrada:

7
2 1 4 3
6

a cor 7 estará na posicão 0, a cor 2 na posicão 1, a cor 1 na posicão 2, a cor 4 na posicão 3, a cor 3 na posicão 4 e a cor 6 na posicão 5.

Como representar um cubo?

Uma maneira de representarmos o cubo, seria criarmos um registro com as posições numeradas do cubo, como foi explanado acima, e uma variável que diz se esse cubo já é igual a algum outro do conjunto dado na entrada (será importante na hora de contar o número de cubos diferentes). Minha sugestão é a seguinte:

 typedef struct _cubo{
    int lados[6];
    int igual;
 }cubo;

O principal desafio

O principal desafio deste programa consiste em comparar dois cubos e saber se eles são iguais. Para isso teremos que realizar em cada cubo as possíveis rotações e comparar com outro cubo para saber se eles são iguais. As rotações possíveis são na horizontal, na vertical e no eixo.

Detalhes de implementação

Sugiro dividir as tarefas. Podemos criar 3 funções, que recebem como entrada um vetor com as cores, cada uma realizando um tipo de rotação.

A primeira função seria a de rotação na horizontal. Basta que troquemos as posições das cores no cubo.

 void rotacionar_horizontal(int lados[6]){
    int aux[6];
    int i;
    for (i=0;i<6;i++) aux[i]=lados[i];
    lados[0]=aux[2];
    lados[2]=aux[5];
    lados[4]=aux[0];
    lados[5]=aux[4];
 }

A segunda função será a de rotação na vertical.

 //Funcao que rotaciona o cubo no sentido vertical1
 void rotacionar_vertical(int lados[6]){
    int i;
    int aux[6];
    for (i=0;i<6;i++) aux[i]=lados[i];
    lados[1]=aux[4];
    lados[2]=aux[1];
    lados[3]=aux[2];
    lados[4]=aux[3];
 }

A terceira será a de rotação no eixo.

 void rotacionar_eixo(int lados[6]){
    int i;
    int aux[6];
    for (i=0;i<6;i++) aux[i]=lados[i];
    lados[0]=aux[5];
    lados[1]=aux[3];
    lados[3]=aux[1];
    lados[5]=aux[0];
 }

Também é interessante usarmos uma função que compara dois vetores e verifica se eles são iguais:

 //Funcao que compara dois vetores e retorna se eles forem iguais
 int compara_vetor(int vetor1[6], int vetor2[6]){
    int i;
    for (i=0;i<6;i++)
        if (vetor1[i]!=vetor2[i]) return 0;
    return 1;
 }

Com as funções de rotação prontas, só falta criar uma função que pega dois cubos e os compara. Podemos fazer isso por rotacionar apenas um deles e comparar com o outro, até achar dois vetores iguais.

 //Funcao que compara dois cubos e retorna se eles sao iguais
 int compara_cubos(cubo a, cubo b){
    int i,j,k;
    for (i=0;i<5;i++){
        if(compara_vetor(a.lados,b.lados)){
            return 1;
        }
        for (j=0;j<5;j++){
                for (k=0;k<5;k++){
                        rotacionar_eixo(a.lados);
                        if(compara_vetor(a.lados,b.lados)) return 1;
                }
                rotacionar_eixo(a.lados);
                rotacionar_vertical(a.lados);
                if (compara_vetor(a.lados,b.lados)){
                   return 1;
                }
        }
        rotacionar_horizontal(a.lados);
    }
    return 0;
 }

Podemos agora contar o numero de cubos diferentes, usando para isso uma função que recebe como entrada um vetor de cubos. É importante nos lembrarmos de atualizar o valor de igual quando acharmos um cubo igual a outro:

 //Funcao que faz a contagem de cubos diferentes no vetor de cubos
 int compara_vetor_cubos(cubo * vetor_cubos, int tam_vetor){
    int i,j;
    int dif=tam_vetor;
    for(i=0;i<tam_vetor;i++){
        if (!vetor_cubos[i].igual){
            for (j=i+1;j<tam_vetor;j++){
                if (!vetor_cubos[j].igual){
                    if (compara_cubos(vetor_cubos[i],vetor_cubos[j])){
                        vetor_cubos[j].igual=1;
                        dif--;
                    }
                }
            }
        }
    }
    return dif;
 }

A nossa função main agora terá que ler as cores do cubo e armazenar num vetor. Depois disso armazenar os cubos em um vetor de cubos. Essas estruturas servirão de entradas para as funções sobre as quais explanamos acima:

 int main (void){
    FILE *in,*out;
    in = fopen("cubos.in","r");
    out = fopen("cubos.sol","w");
    cubo * vetor_cubos;
    int n_cubos,i,j;
    //scanf("%d",&n_cubos);
    fscanf(in,"%d ",&n_cubos);
    while(n_cubos){
        vetor_cubos=(cubo*)malloc(sizeof(cubo)*n_cubos);
        for (i=0; i < n_cubos;i++){
            for (j=0;j < 6; j++){
                //scanf("%d",&vetor_cubos[i].lados[j]);
                fscanf(in,"%d ",&vetor_cubos[i].lados[j]);
            }
            vetor_cubos[i].igual=0;
        }
        //printf("%d\n",compara_vetor_cubos(vetor_cubos,n_cubos));
        fprintf(out,"%d \n",compara_vetor_cubos(vetor_cubos,n_cubos));
        //scanf("%d",&n_cubos);
        fscanf(in,"%d ",&n_cubos);
        free(vetor_cubos);
    }
    fclose(in);
    fclose(out);
    return 0;
 }

Com isso o problema está resolvido.

Contribuído por Ricardo José Sales Júnior - Ciências da Computação - DIMAp - UFRN

---

Veja este problema em: Maratona de Programação (pdf).