O Problema dos peixes

[brunoalves5]

Estava eu a pescar no jogo Metin2 e reparei que estava a fazer algo que seria um bom exercicio de programação para quem gosta de desafios, não sei se conhecem, neste jogo, a pesca é uma boa forma de ganhar dinheiro quando se está a precisar de Yang (moeda do jogo), então o problema é o seguinte:

No jogo, tenho um inventário quadriculado com espaço para os meus itens, e os peixes que são pescados vão preenchendo esses espaços, ou seja, imaginemos um inventário com as dimensões 5x9 em que os espaços estão preenchidos com peixes ordenados do menos raro para o mais raro e identificados por um nº (quanto maior o nº, mais raro é o peixe), um '0' representa um espaço livre e os primeiros N espaços estão sempre livres (N é o nº de peixes que vão ser pescados):

Exemplo 1:

0 1 1 1 1

1 1 2 3 3

3 4 4 7 7

7 7 8 9 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

Exemplo 2:

0 0 1 1 1

1 1 1 2 3

4 5 5 6 6

7 8 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

Dos 0's que aparecem asseguir aos peixes, apenas estão livres os N primeiros 0's, os restantes são espaços ocupados com outros itens do jogador que não são peixes.

Quando eu pescar todos os peixes, estes vão para os primeiros espaços livres, por exemplo, para o Exemplo 2, imaginemos que pesquei um peixe 5 e um peixe 3, a primeira linha do inventário ficaria: "5 3 1 1 1".

Agora o problema:

Depois de ter os primeiros espaços livres ocupados eu quero voltar a ordenar os peixes, utilizando os N primeiros espaços asseguir aos peixes como auxiliares e utilizando o mínimo de movimentos possíveis, ou seja, para o Exemplo 2 o inventário ficaria assim:

1 1 1 1 1

1 2 3 3 4

5 5 5 6 6

7 8 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

E precisaria de um mínimo de 9 movimentos.

Neste exemplo, os peixes a verde são os que foram movidos, os 0's a vermelho são os espaços de onde eles vieram e os 0's rasurados são os espaços ocupados por outros itens que não podem ser utilizados como auxiliares.

0 mov:---->2 mov:---->4 mov:---->6 mov:--->7 mov:---->8 mov:---->9 mov:

5 3 1 1 1->0 0 1 1 1->1 1 1 1 1->1 1 1 1 1->1 1 1 1 1->1 1 1 1 1->1 1 1 1 1

1 1 1 2 3->1 1 1 2 3->1 0 0 2 3->1 2 3 0 0->1 2 3 3 0->1 2 3 3 4->1 2 3 3 4

4 5 5 6 6->4 5 5 6 6->4 5 5 6 6->4 5 5 6 6->4 5 5 6 6->0 5 5 6 6->5 5 5 6 6

7 8 0 0 0->7 8 5 3 0->7 8 5 3 0->7 8 5 3 0->7 8 5 0 0->7 8 5 0 0->7 8 0 0 0

0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0

0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0

0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0

0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0

0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0->0 0 0 0 0

Tarefa:

Dado o nº N de peixes a pescar, o inventário com L linhas e C colunas e os peixes que foram pescados, quero saber qual o menor nº de movimentos necessários para reordenar os peixes.

Input:

2

5 9

0 0 1 1 1

1 1 1 2 3

4 5 5 6 6

7 8 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

5 3

Output:

9

Edited May 27, 2012 at 09:31 AM by brunoalves5

[polska]

Original 👍

[brunoalves5]

Aqui está a minha solução para o problema, penso que funciona em todos os casos (pelo menos funcionou em todos os que testei 😁 ), no entanto é muito provável que tenha lacunas e se tiverem melhores soluções agradecia que partilhassem 👍 .

#include <cstdlib>
#include <iostream>
using namespace std;
int i,n,inv[100000],aux,peixe,j,l,c,mov,k,np,s,peixes_tipo[10000],faltam,x,y,jj;
int main()
{
   scanf("%d%d%d",&n,&l,&c);
   k=0;
   np=1;
   s=0;
   for(i=1;i<=l*c;i++){//-------------------------le o inventário e verifica onde começam os espaços auxiliares
scanf("%d",&inv[i]);
       if(inv[i]!=0)
           k=1;
       else{
           if((k==1)&&(inv[i]==0)){
               aux=i;//primeiro epaço auxiliar
               k++;
           }
       }
       if(i>n+1){//-------------------------verifica quantos peixes há de cada tipo
           if((inv[i]==inv[i-1])&&(inv[i]!=0))
                np++;
           else{
               if (inv[i-1]!=0){
                   s++;
                   peixes_tipo[inv[i-1]]=np;
                   np=1;
               }
           }
       }
   }
   k=1;
   for(i=1;i<=n;i++){//---Coloca os peixes nos espaços livres
       scanf("%d",&inv[i]);
   }
   s=0;
   mov=0;
   faltam=n;
   for(i=1;i<=n;i++){//ciclo que vai ver quais dos peixes que foram pescados ja se encontram nas posiçoes certas
       if(inv[i]>inv[n+i-s]){
inv[aux+(i-1)-s]=inv[i];
           inv[i]=0;
           mov++;
           //printf("%d->%d\n",i,aux+(i-1)-s);
       }else{
faltam--;
           s++;
}
   }
   inv[0]=-1;
   for(i=1;i<=n;i++){//preenche os primeiros n espaços
       if(inv[i]==0){
           k=0;              
           for(j=n+1;inv[j]==0;j++);
           x=inv[j];
           jj=j;
           for(j=aux;j<=aux+n-1;j++){
               if((inv[i-1]<=inv[j])&&(x>=inv[j])&&(inv[j]!=0)){
                   k=1;
                   inv[j]=0;
                   inv[i]=x;
                   faltam--;
                   mov++;
                   //printf("%d->%d\n",j,i);
                   break;
}

}
if(k==0){  
j=jj;    
while(inv[j]==x){
j++;
}
j--;
inv[j]=0;
inv[i]=x;
mov++;
//printf("%d->%d\n",j,i);
}
}
   }
   if(faltam>0){
for(i=n+1;i<l*c;i++){//ordena o resto dos peixes
if(inv[i]==0){
k=0;          
for(j=i+1;inv[j]==0;j++);
x=inv[j];
jj=j;
for(j=aux;j<=aux+n-1;j++){
if((inv[i-1]<=inv[j])&&(x>=inv[j])){
k=1;
inv[j]=0;
inv[i]=x;
faltam--;
mov++;
//printf("%d->%d\n",j,i);
break;
}
}
if(k==0){    
j=jj;
while(inv[j]==x){
j++;
}
j--;
inv[j]=0;
inv[i]=x;
mov++;
//printf("%d->%d\n",j,i);
}
}
if(faltam==0)
break;
}
   }  
   /*for(i=1;i<=c*l;i++){
printf("%d ",inv[i]);
   }*/
   printf("%d\n",mov);
   system("PAUSE");
   return EXIT_SUCCESS;
}

Esqueçam a parte onde verifico quantos peixes há de cada tipo porque não serviu de nada, eu comecei a fazer de uma maneira e acabei de outra e não alterei o código 😛 .

Edited May 30, 2012 at 10:35 AM by Warrior