Domino massimale

di

Fase Territoriale 2011

Sono date N tessere di domino, dove ogni tessera contiene due numeri compresi da 0 a 6 in corrispondenza delle sue due estremità.
Le tessere possono essere ruotate e la regola impone che due tessere possono essere concatenate se le loro estremità in contatto hanno inciso lo stesso numero.

Aiuta a trovare il maggior numero di tessere che si possono concatenare a formare un’unica catena: non è detto che si riescano sempre a usare tutte le tessere; inoltre, possono esserci due o più tessere uguali a meno di rotazioni.

Dati di input

Il file input.txt è composto da N+1 righe.
La prima riga contiene l’intero positivo N, il numero delle tessere a disposizione.
Ciascuna delle successive N righe contiene due interi positivi (compresi da 0 a 6) separati da una spazio, che rappresentano i numeri incisi sulle estremità delle tessere.

Dati di output

Il file output.txt è composto da una sola riga contenente il massimo numero di tessere che possono essere concatenate con le regole del domino.

Assunzioni

  • 2 ≤ N ≤ 10.

Esempi di input/output

input.txt output.txt
6
3 0
4 0
2 6
4 4
0 1
1 0		 5 
/*
	www.valcon.it
	OII 2011 - Fase territoriale - Domino massimale
*/
#include
#include

#define NMAX 10

using namespace std;

struct tessera{ int sx, dx; };

tessera tesSX[NMAX];
tessera tesDX[NMAX];
tessera tesSol[NMAX];
bool    usata[NMAX];

int N;	
int risposta=0;

void soluzione(int num)
{
	if(num > risposta)
	    risposta=num;
	
	for(int i=0; i < N; i++)
	{
		if(usata[i] == false)
		{
			if(tesSol[num-1].dx == tesSX[i].sx)
		    { 
		    	usata[i]=true; 
				tesSol[num]=tesSX[i]; 
				soluzione(num+1); 
				usata[i]=false;
		    }   
	    	if(tesSol[num-1].dx == tesDX[i].sx) 
   	        {
		    	usata[i]=true; 
				tesSol[num]=tesDX[i]; 
				soluzione(num+1); 
				usata[i]=false;
	    	}
		}
	}
}

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
	
	fin >> N;	
	int sin, des;
	for(int i=0; i < N; i++)
	{
		fin >> sin >> des;		
		
		tesSX[i].sx=sin; tesSX[i].dx=des; 
		tesDX[i].sx=des; tesDX[i].dx=sin; 
		usata[i]=false;
	}	
	
	for(int i=0; i < N; i++)
	{
		usata[i]=true;
		tesSol[0]=tesSX[i]; soluzione(1);
		tesSol[0]=tesDX[i]; soluzione(1);
		usata[i]=false;
	}	
	
	fout << risposta;	
	return 0;
}