Tävlingsprogrammering/Uppgifter/Dela tårtan

Dela tårtan

Du får en 5x5 matris som föreställer en tårta indelad i 25 områden. Varje område har en bokstav (vald bland A-E) som markerar dess "innehåll" (aprikos, banan, chokladbit, druva eller extragrädde). Dela tårtan i fem delar så att alla delar är sammanhängande, lika stora och innehåller samma saker.

Indata

5 rader vardera innehållande 5 tecken, valda bland A-E (men alla behöver inte förekomma). Antalet bokstäver av ett visst slag är alltid delbart med fem.

Utdata

Programmet ska skriva ut 5 rader med 5 tecken (valda bland 1-5), föreställande samma tårta som i indatan men där varje siffra nu motsvarar en tårtbit. Du kan räkna med att det alltid finns minst en lösning och det spelar ingen roll hur du numrerar tårtbitarna.

Exempel: Indata

CBCAB
ABCAA
ACACB
ACACA
BCCCA

Exempel: Utdata

Exempel: Förklaring

Varje tårtbit är sammanhängande och innehåller samma saker: två aprikoser, en banan och två chokladbitar.

Lösning

Vid första anblick kan uppgiften se svår ut och att en lösning som rekurserar och testar "alla möjliga fall" skulle ta alldeles för lång tid på sig. Faktum är att om man alltid kontrollerar att en bit "passar" innan man lägger dit den, dvs. att man har ringat in precis så många A,B,C,D,E som ska vara med, kommer det gå väldigt snabbt att komma fram till en lösning. Det är bra att man bara behöver skriva ut den första lösningen man kommer fram till, och att inte uppgiften var t.ex. Hur många sätt finns det att dela in tårtan på? Det finns nämligen oftast väldigt många sätt att dela in tårtan på.

#include <iostream>
#include <cstdio>
using namespace std;

char tarta[5][5][2];//första nivån är tårtan, 2:ra - bitarna vi ska dela den i.
short antalBokst[5];//antal A:n, B:n osv

struct bit
{
  short antalBitar;
  pair<short,short> allaBitar [5];//alla bitarna.
  char siffra;//kanske inte
  short behovs[5];//antal A:n, B:n... som behövs.
  bit(char s,short x, short y)
  {
    antalBitar=1;
    siffra=s;
    allaBitar[0]=make_pair(x,y);
    for(int i=0;i<5;i++)
      behovs[i]=antalBokst[i];
    behovs[tarta[x][y][0]-'A']-=1;
  }
void  addRuta(short x,short y)
  {
    allaBitar[antalBitar]=make_pair(x,y);
    antalBitar++;
    behovs[tarta[x][y][0]-'A']-=1;
    tarta[x][y][1]=siffra;
  }
  void  deleteRuta( )
  {
    short x = allaBitar[antalBitar-1].first;
    short y = allaBitar[antalBitar-1].second;
    antalBitar--;
    behovs[tarta[x][y][0]-'A']+=1;
    tarta[x][y][1]=0;
  }
};

bool hittaBit(bit B)
{
  
  //hittar en ny bit. Kolla hur mycket saker som finns, testar sätta en ny ruta runt varje existerande.
  if(B.antalBitar==5)
    {
      //försök hitta ny bit:
      for(int i=0;i<5;i++)
	for(int j=0;j<5;j++)
	  if(tarta[i][j][1]==0){
	    tarta[i][j][1]=B.siffra+1;
	    if(! hittaBit(bit(B.siffra+1,i,j)))
	      {
		tarta[i][j][1]=0;
		return false;
	      }
	    else
	      return true;
	    
	  }
      return true; //true;//om det inte finns nårga bitar kvar är vi klara :)
    }
  
  for(int i=0;i<B.antalBitar;i++)
    {
      int x=B.allaBitar[i].first;
      int y=B.allaBitar[i].second;
      int yleft=y-1;
      if(yleft>=0 && B.behovs[tarta[x][yleft][0]-'A']>0 && tarta[x][yleft][1]==0)
	{
	  B.addRuta(x,yleft);
	  if(!hittaBit(B))
	    B.deleteRuta();
	  else return true;
	}
     }
  for(int i=0;i<B.antalBitar;i++)
    {
      int x=B.allaBitar[i].first;
      int y=B.allaBitar[i].second;
      int xup=x-1;
      if(xup>=0 && B.behovs[tarta[xup][y][0]-'A']>0 && tarta[xup][y][1]==0)
	{
	  B.addRuta(xup,y);
	  if(!hittaBit(B))
	    B.deleteRuta();
	  else return true;
	}
    }

  for(int i=0;i<B.antalBitar;i++)
    {
      int x=B.allaBitar[i].first;
      int y=B.allaBitar[i].second;
      int xdown=x+1;
      if(xdown<=4 && B.behovs[tarta[xdown][y][0]-'A']>0 && tarta[xdown][y][1]==0)
	{
	  B.addRuta(xdown,y);
	  if(!hittaBit(B))
	    B.deleteRuta();
	  else return true;
	}
     }
  for(int i=0;i<B.antalBitar;i++)
    {
      int x=B.allaBitar[i].first;
      int y=B.allaBitar[i].second;
      int yright=y+1;
      if(yright<=4 && B.behovs[tarta[x][yright][0]-'A']>0 && tarta[x][yright][1]==0)
	{
	  B.addRuta(x,yright);
	  if(!hittaBit(B))
	    B.deleteRuta();
	  else return true;
	}
     }


  B.deleteRuta();
  return false;
}

  
void zolve(char bit_nr)
{
  //hitta en lagom pajbit, kapa den, zolva resten, testa en annan tårtbit osv
  //ta 1:a icketomma rutan, kolla runt den
  tarta[0][0][1]='1';
  hittaBit(bit('1',0,0));
}


int main()
{
  for(int i=0;i<5;i++)antalBokst[i]=0;
  
  //läsa indata och zolve(1):a
  for(int i=0;i<5;i++)
    for(int j=0;j<5;j++)
      {
	cin>>tarta[i][j][0];
	antalBokst[tarta[i][j][0]-'A']++;
	tarta[i][j][1]=0;
      }
  //yeah! nu har vi en tårta! mmm... tårta...

  for(int i=0;i<5;i++)
    antalBokst[i]/=5; //nu vet vi hur många det ska va i varje bit
  
  zolve('1');
  
  //skriv ut tårta!
  for(int i=0;i<5;i++){
    for(int j=0;j<5;j++)
      printf("%c", tarta[i][j][1]);
    cout<<endl;
  }
}