I'm working on a recursive code that increments a variable every time I find a solution to my problem (I do not think it's relevant or necessary to explain the problem at hand).
Well, the output of my program is supposed to print this counter with the number of solutions.
I've already been able to give you the right answer. However, when I removed the printf I had to debug, I realized that if I removed them all, the final result would be 0. After a little research I realized that I have to have printf("\n\n"); in the recursive function for that the expected output is printed.
Any reason more general?
EDIT:
I already figured out what was wrong. there is a part where I am declaring a int rectLOCAL[8]; array but I do not initialize it to 0 as I was supposed to have done, so I was having trouble comparing the next cycle.
By entering memset(rectLOCAL,0,8*sizeof(int)); already makes the code work as expected.
Follow the code:
/*
_____ ____ _____ _____
| | | | | |
| 1 | | | 1 | 2 |
| | | |_____|_____|
----- 3 | | 3 |
| | | |___________|
| 2 | |
|_____|____|
___________
____ _____ | 3 |
| | | |_____ _____|
| | 1 | | | |
| | | | 1 | 2 |
| 3 ----- |_____|_____|
| | |
| | 2 |
|____|_____|
*/
/*
Description
Fitting rectangles is a game where the player is given a set of small rectangles and needs to create a large
rectangle, using all small rectangles exactly once.
For example, if the player is given the following 3 small rectangles: 1,2,3 seen above
A few possible ways to make a large rectangle would be: the 4 combinations above
Your task is to find out how many distinct configurations there are to create a large rectangle given the list
of small rectangles.
DISTINCT* por exemplo se o rectangulo 1 e 2 estiverem trocados não conta como +1 solução.
Two configurations are not distinct if, by removing the indices of the small rectangles, we are not able to
visually distinguish them; this is the case for configurations A and D.
Note that you can rotate rectangles, as can be seen in configuration C
Input
Each test case starts with a line with an integer 1 ≤ n ≤ 8, the number of small rectangles.
The following n lines contain two integers each, w i and h i , the width and height of the ith rectangle
respectively, 1 ≤ i ≤ n .
Output
For each test case, print the number of distinct configurations, it is guaranteed that no more than 10000
solutions exist.
Example
Example input:
3
40 120
50 60
50 60
Example output:
4
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <unistd.h>
/*
rectSizes[][0] -- x
rectSizes[][1] -- y
rectSizes[][2] -- se esta ocupado
*/
int rectSizes[8][3];
int referenceP[9][2];
int nRect;
int rect;
int areaMax;
int teste;
int flagRepetidos;
int placeRect(int mode, int x, int y, int rect, int refPoints[9][2],int RefPoints, int xMax, int yMax);
/*coloca os rectangulos
x,y é o ponto a apagar
rect é o rectangulo a ser ocupado
refPoints atualiza a cada chamada de recursão
o numero max de pontos de ref é nrect+1
*/
int allOcupied(){
int i;
for (i = 0; i<nRect; i++){
if (rectSizes[i][2]==0){
return 0;
}
}
return 1;
}
/*verifica se os rectangulos ja foram todos usados*/
int checkRP(int refPoints[9][2]){
int i;
int counter=0;
/*printf("A verificar PR:\n");*/
for(i=0; i<9;i++){
if(refPoints[i][0]!=0 || refPoints[i][1]!=0){
counter++;
}
}
if (counter==2){
return 1;
}
return 0;
}
/*devolve o index do ponto de referencia seguinte
x,y são os pontos do ponto de referencia a passar
devolve -1 se o ponto de referencia estiver num eixo
*/
int RPdepois(int RP[9][2], int x,int y,int xMax){
int j;
int ponto = -1;
int minX = xMax;
for(j=0;j<9;j++){
if(RP[j][0] == 0 && RP[j][1]==0){break;}
if(RP[j][0] == x && RP[j][1]==y){continue;}
if((RP[j][0]-x)>0 && (RP[j][0]-x)<=minX){
minX = (RP[j][0]-x);
ponto = j;
}
}
return ponto;
}
/*devolve o index do ponto ponto de referencia anterior
x,y são os pontos do ponto de referencia a passar
devolve -1 se o ponto de referencia estiver num eixo
*/
int RPantes(int RP[9][2], int x, int y,int yMax){
int j;
int ponto = -1;
int minY = yMax;
for(j=0;j<9;j++){
if((RP[j][0] == 0 && RP[j][1]==0)){break;}
if((RP[j][0] == x && RP[j][1]==y)){continue;}
if((RP[j][1]-y)>0 && (RP[j][1]-y)<=minY){
minY = (RP[j][1]-y);
ponto = j;
}
}
return ponto;
}
/*faz update do Ymax e Xmax*/
int updatexMax(int h, int w, int x, int y, int xMax){
int l = xMax;
if(l < x+w){
l = x+w;
}
return l;
}
int updateyMax(int h, int w, int x, int y, int yMax){
int l = yMax;
if(l < y+h){
l = y+h;
}
return l;
}
int placeRect(int mode, int x, int y, int rect, int refPoints[9][2],int RefPoints, int xMax, int yMax){
int k = 0;
int j;
int RP[9][2];
int ymaxlocal = yMax;
int xmaxlocal = xMax;
int temp;
if(mode == 1){
temp = rectSizes[rect][0];
rectSizes[rect][0] = rectSizes[rect][1];
rectSizes[rect][1] = temp;
}
memcpy(RP, refPoints,18*sizeof(int));
rectSizes[rect][2] = 1;
/*actualiza os maximos X ou Y caso seja necessario*/
xmaxlocal = updatexMax(rectSizes[rect][1], rectSizes[rect][0], x, y, xmaxlocal);
ymaxlocal = updateyMax(rectSizes[rect][1], rectSizes[rect][0], x, y, ymaxlocal);
/* Caso a area com os x,y maximos ultrapasse a area maxima possivel para os rectangulos dados, volta de imediato atras*/
if (areaMax<xmaxlocal*ymaxlocal){
rectSizes[rect][2] = 0;
if(mode == 1){
temp = rectSizes[rect][0];
rectSizes[rect][0] = rectSizes[rect][1];
rectSizes[rect][1] = temp;
}
return 0;
}
if(RP[0][0] == 0 && RP[0][1] == 0){
RP[0][0] = rectSizes[rect][0];
RP[1][1] = rectSizes[rect][1];
RefPoints++;
}
else{
while((RP[k][1] != 0) || (RP[k][0] != 0)){
if(RP[k][1] == y && RP[k][0] == x){
int index1 = RPantes(RP, x, y, ymaxlocal);
int index2 = RPdepois(RP, x, y, xmaxlocal);
int height = rectSizes[rect][1];
int width = rectSizes[rect][0];
/*remove ponto de ref e adiciona dois*/
if(RP[k][1] == 0){
if ((RP[k][1]+height) == RP[index1][1]){
RP[k][0] += width;
}
else{
RP[RefPoints][0] = RP[k][0]+rectSizes[rect][0];
RP[RefPoints][1] = RP[k][1];
RP[k][1] += rectSizes[rect][1];
RefPoints++;
}
}
else if(RP[k][0] == 0){
if ((RP[k][0]+width) == RP[index2][0]){
RP[k][1] += height;
}
else{
RP[RefPoints][0] = RP[k][0];
RP[RefPoints][1] = rectSizes[rect][1]+RP[k][1];
RP[k][0] += rectSizes[rect][0];
RefPoints++;
}
}
else{
if(((RP[k][0]+width) == RP[index2][0]) && ((RP[k][1]+height) == RP[index1][1])){
RP[k][1] = 0;
RP[k][0] = 0;
RefPoints--;
}
else if ((RP[k][0]+width) == RP[index2][0]){
RP[k][1] += height;
}
else if ((RP[k][1]+height) == RP[index1][1]){
RP[k][0] += width;
}
else{
RP[k][1] += rectSizes[rect][1];
RP[RefPoints][1] = RP[k][1];
RP[RefPoints][0] = RP[k][0]+rectSizes[rect][0];
RefPoints++;
}
}
break;
}
k++;
}
}
/*condicao de paragem*/
if (allOcupied()){
if(mode == 1){
temp = rectSizes[rect][0];
rectSizes[rect][0] = rectSizes[rect][1];
rectSizes[rect][1] = temp;
}
if (areaMax==xmaxlocal*ymaxlocal && checkRP(RP)){
teste+=1;
rectSizes[rect][2] = 0;
return 0;
}
else{
rectSizes[rect][2] = 0;
return 0;
}
}
/* vamos fazer apenas para o caso onde o rectangulo posto é mais pequeno ou igual ou anterior*/
int rectLOCAL[8];
/*EDIT*/
memset(rectLOCAL,0,8*sizeof(int));
int p;
int q;
int flagA;
int flagB;
int mode1b;
int mode1a;
int flag;
int o;
for(j=0;j<nRect;j++){
flag = 0;
if(rectSizes[j][2] == 1){continue;}
/*sem este ciclo, o resultado passa a dar mal no entanto não se altera com a presença do \n*/
for(o=0;o<nRect;o++)
{
if(o==j){
continue;
}
if(rectLOCAL[o]==1){
if((rectSizes[o][0] == rectSizes[j][0] && rectSizes[o][1] == rectSizes[j][1]) || (rectSizes[o][0] == rectSizes[j][1] && rectSizes[o][1] == rectSizes[j][0])){
flag =1;
break;
}
}
}
if(flag==1){continue;}
rectLOCAL[j]=1;
for(k=0;k<RefPoints;k++){
flagA = 0;
flagB = 0;
mode1b = 0;
mode1a = 0;
/*
q index do ponto de referencia anterior ao ponto de referencia x,y
p index do ponto de referencia seguinte ao ponto de referencia x,y
*/
p = RPdepois(RP,RP[k][0],RP[k][1], xmaxlocal);
q = RPantes(RP,RP[k][0],RP[k][1], ymaxlocal);
if(p==-1){
flagA = 1;
}
else {
if(RP[k][0]+rectSizes[j][0] <= RP[p][0]){
mode1a = 1;
flagA = 1;
}
if(RP[k][0]+rectSizes[j][1] <= RP[p][0]){
mode1b = 1;
flagA = 1;
}
}
if(q==-1){
flagB = 1;
}
else{
if(RP[k][1]+rectSizes[j][1] <= RP[q][1]){
mode1a = 1;
flagB = 1;
}
if(RP[k][1]+rectSizes[j][0] <= RP[q][1]){
mode1b = 1;
flagB = 1;
}
}
/*verifica se o rectangulo fica mais alto/comprido do que os rectangulos à sua volta
e caso seja passa o caso à frente*/
if(flagA==1 && flagB==1){
/*caso esteja a ser testado com as coordenadas invertidas*/
if(mode == 1){
temp = rectSizes[rect][0];
rectSizes[rect][0] = rectSizes[rect][1];
rectSizes[rect][1] = temp;
}
/*verifica se é um quadrado*/
if(rectSizes[j][0] != rectSizes[j][1]){
if(mode1a==1){placeRect(0,RP[k][0],RP[k][1],j,RP,RefPoints,xmaxlocal,ymaxlocal);}
if(mode1b==1){placeRect(1,RP[k][0],RP[k][1],j,RP,RefPoints,xmaxlocal,ymaxlocal);}
}
else{
/* se for um quadrado só precisa de executar uma vez*/
placeRect(0,RP[k][0],RP[k][1],j,RP,RefPoints,xmaxlocal,ymaxlocal);
}
}
if(mode == 1){
temp = rectSizes[rect][0];
rectSizes[rect][0] = rectSizes[rect][1];
rectSizes[rect][1] = temp;
}
}
}
if(mode == 1){temp = rectSizes[rect][0];
rectSizes[rect][0] = rectSizes[rect][1];
rectSizes[rect][1] = temp;}
rectSizes[rect][2] = 0;
return 0;
}
int main(void)
{
int i;
int rp[9][2];
int o;
memcpy(rp, referenceP,18*sizeof(int));
scanf("%d", &nRect);
int temp;
for(i=0; i<nRect;i++)
{
scanf("%d %d", &rectSizes[i][0],&rectSizes[i][1]);
if(rectSizes[i][0]<rectSizes[i][1]){
temp = rectSizes[i][0];
rectSizes[i][0] = rectSizes[i][1];
rectSizes[i][1] = temp;
}
/*calcular area para saber area maxima*/
areaMax+=rectSizes[i][0]*rectSizes[i][1];
}
for(i=0; i<nRect;i++)
{
for(o=0;o<i;o++){
if(i==o){continue;}
if((rectSizes[o][0] == rectSizes[i][0] && rectSizes[o][1] == rectSizes[i][1]) || (rectSizes[o][0] == rectSizes[i][1] && rectSizes[o][1] == rectSizes[i][0]) ){
flagRepetidos = 1;
}
}
if(flagRepetidos==1){
flagRepetidos = 0;
continue;
}
if(rectSizes[i][0] == rectSizes[i][1]){;
placeRect(0,0,0,i,rp,1,0,0);
}
else{
placeRect(0,0,0,i,rp,1,0,0);
placeRect(1,0,0,i,rp,1,0,0);
}
}
printf("%d\n",teste);
return 0;
}