Problema Cuburilor

Problemă:

Se dau n cuburi numerotate 1,2,…,n, de laturi l_i si culori c_i, i=1,2,…,n (fiecare culoare este codificată printr-un caracter).

Să se tipărească toate turnurile care se pot forma luând p cuburi din cele n disponibile, astfel încât laturile cuburilor din turn să fie în ordine crescătoare iar culorile a oricare 2 cuburi alăturate din turn să fie diferite.

Exemplu: Pentru un număr total de 4 cuburi, considerăm cuburile 1,2,3,4 de laturi (8,4,9,6) și culori (‘r’,’v’,’g’,’v’). Turnurile de câte 3 cuburi care îndeplinesc cerințele din enunț sunt [2,1,3], [4,1,3].

Implementare:

Cod Sursa C++

// CuburiCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include<stdio.h>
#include<string.h>
#include<iostream>
 
using namespace std;
 
int x[50],k,valid,n,m;
int dim[50];char cul[50][20];
 
void citire() /*citim datele de intrare*/
{
	cout<<"numarul total de  cuburi n= ";
	cin>>n;
	for(int i=1;i<=n;i++)
	{  
		cout<<"dimensiunea laturii pentru cubul "<<i<<": ";
		cin>>dim[i];
		cout<<"culoarea cubului "<<i<<": ";
		cin>>cul[i];
	}
	cout<<"numarul de cuburi din turn m= ";
	cin>>m;
}
 
void posibil(int k,int &valid)
{
	valid=1;
	for (int i=1;i<k;i++) 
		if(x[i]==x[k])
			valid=0; /*acelasi cub nu poate fi pus in turn de doua ori*/
	if(k>1)
		if(strcmp(cul[x[k-1]],cul[x[k]])==0) 
			valid=0;/*doua cuburi alaturate nu pot avea aceiasi culoare*/
	if(k>1)
		if(dim[x[k-1]]<dim[x[k]]) 
			valid=0;/*un cub cu latura mai mare nu poate fi pus peste un cub cu latura mai mica*/
}
 
int solutie(int k)
{
	/*avem solutie cand am reusit sa asezam in turn m cuburi*/
	if(k==m)
		return 1;
	else 
		return 0;
}
 
void afisare(int k)
{
	/*afisam solutia specificand pentru fiecare cub dimensiunea laturii si culoare*/
	for(int i=1;i<=k;i++)
       cout<<x[i]<<"("<<dim[x[i]]<<" "<<cul[x[i]]<<") ";
		cout<<endl;
}
 
void back()
{
	k=1;
	x[k]=0;
	while(k>0)
	{
		valid=0;
		while(!valid && x[k]<n)
		{
			x[k]=x[k]+1;
			posibil(k,valid);
		}
		if(!valid)
			k--;
        else if(solutie(k)) 
			afisare(k);
        else 
		{
			k++;
			x[k]=0;
        }
	}
}
 
int main()
{
	citire();
	back();
	afisare(k);
	system("Pause");
}

Rezultat: