/*                adcpenta.c                                           *
*                                                                      *
*      Copyright (C) Alain DE CESARE - Paris - janvier 2000            *
*               Alain.Decesare@imed.jussieu.fr                         *
*                                                                      *
*      Ce fichier source C peut etre obtenu et distribue gratuitement. *
*      Tout possesseur d'une copie peut la modifier et/ou la           *
*      distribuer sous reserve que la presente notice reste            *
*      incluse. Des versions compiles de ce source peuvent etre        *
*      distribuees a condition d'etre accompagnees du fichier source.  *
*      Ni ce fichier source, ni un executable contruit totalement ou   *
*      partiellement a partir de ce source ne peuvent etre vendus      *
*      sans le consentement de l'auteur.                               *
*                                                                      */

/*************************************************************************
*
*		Section 1 : include					*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

/*************************************************************************
*
*		Section 2 : define					*/

#define HMAX 20
#define WMAX 30
#define LETTRESYMPAIR 'X'
#define LETTRESYMIMPAIR 'P'

#define TT 4000 /* majorant du nombre total de pieces */
#define ALLOCSOLUCES 512

/*************************************************************************
*
*		Section 3 : typedef					*/

typedef char resultat[60];

typedef struct
{
	int y[5], x[5];	/* coordonnees des cases */
	char nom;
}	pentambase;

typedef struct
{
	long l[HMAX];	/* motif binaire */
	int base;	/* pentamino de base */
	int cases[5];   /* numero des cases */
}	pm;

/*************************************************************************
*
*		Section 4 : Variable initialisees			*/

static const pentambase BASE[12] =
{
	{ { 0, 0, 1, 1, 1 }, { 0, 2, 0, 1, 2}, 'U' },
	{ { 0, 1, 1, 1, 2 }, { 1, 0, 1, 2, 1}, 'X' },
	{ { 0, 1, 2, 2, 2 }, { 0, 0, 0, 1, 2}, 'V' },
	{ { 0, 1, 2, 3, 4 }, { 0, 0, 0, 0, 0}, 'I' },
	{ { 0, 1, 2, 3, 3 }, { 0, 0, 0, 0, 1}, 'L' },
	{ { 0, 1, 1, 2, 3 }, { 1, 0, 1, 0, 0}, 'N' },
	{ { 0, 0, 1, 1, 2 }, { 1, 2, 0, 1, 1}, 'F' },
	{ { 0, 0, 0, 1, 2 }, { 0, 1, 2, 1, 1}, 'T' },
	{ { 0, 1, 1, 2, 2 }, { 0, 0, 1, 1, 2}, 'W' },
	{ { 0, 1, 1, 2, 3 }, { 1, 0, 1, 1, 1}, 'Y' },
	{ { 0, 0, 1, 2, 2 }, { 0, 1, 1, 1, 2}, 'Z' },
	{ { 0, 0, 1, 1, 2 }, { 0, 1, 0, 1, 0}, 'P' }
};

/*************************************************************************
*
*		Section 5 : Variables globales				*/

static int H, W, S, SOL_ALLOUEES, SOL_TROUVEES;
static int NOEUD, NOEUDPIECE, NOEUDCASE, NOEUDECHEC, NOEUDFIN;
static int YCASE[60], XCASE[60];
static int NUMCASE[HMAX][WMAX];
static int CCOMPTE[60], PCOMPTE[12], CASES[60], GRAPHE[HMAX * WMAX];
static long MCASE[60];
static pm TOUS[TT];
static pm **RESTE[12];
static resultat *SOLUTIONS, RES;

/*************************************************************************
*
*		Section 6 : Recherche des composantes connexes		*/

static int connexe(int d, int plein)
{
	int lst[60];
	int n, nl, trou, k, u, t, limite;

	trou = GRAPHE[d];
	GRAPHE[d] = plein;
	lst[0] = d;
	n = nl = 1;
	limite = (H - 1) * W;

	while(nl > 0)
	{
		nl--;
		k = lst[nl];
		u = k % W;

		if(u > 0)
		{
			if(GRAPHE[t = k - 1] == trou)
			{
				GRAPHE[t] = plein;
				lst[nl++] = t;
				n++;
			}
		}

		if(u + 1 < W)
		{
			if(GRAPHE[t = k + 1] == trou)
			{
				GRAPHE[t] = plein;
				lst[nl++] = t;
				n++;
			}
		}

		if(k >= W)
		{
			if(GRAPHE[t = k - W] == trou)
			{
				GRAPHE[t] = plein;
				lst[nl++] = t;
				n++;
			}
		}

		if(k < limite)
		{
			if(GRAPHE[t = k + W] == trou)
			{
				GRAPHE[t] = plein;
				lst[nl++] = t;
				n++;
			}
		}

	}

	return n;
}

static int scangraphe(pm *pmc, int grnum)
{
	int k, d, trou, nr, nn;

	trou = GRAPHE[YCASE[pmc->cases[0]] * W + XCASE[pmc->cases[0]]];
	for(k = 0; k < 5; k++)
		GRAPHE[YCASE[pmc->cases[k]] * W + XCASE[pmc->cases[k]]] = -1;

	for(nn = k = 0; k < S; k++)
	{
		d = YCASE[k] * W + XCASE[k];
		if(GRAPHE[d] != trou) continue;

		nr = connexe(d, grnum + nn);

		if((nr % 5) != 0)
		{
			for(k = H * W - 1; k >= 0 ; k--)
				if(GRAPHE[k] >= grnum)
					GRAPHE[k] = trou;

			for(k = 0; k < 5; k++)
				GRAPHE[YCASE[pmc->cases[k]] * W +
						XCASE[pmc->cases[k]]] = trou;

			return 0;
		}

		nn++;
	}

	return grnum + nn;
}

/*************************************************************************
*
*		Section 7 : Initialisations diverses et variees		*/

static void initrectcases(void)
{
	int i, j, k;

	for(j = 0; j < HMAX; j++)
		for(i = 0; i < WMAX; i++)
			NUMCASE[j][i] = -1;

	for(k = j = 0; j < H; j++)
	{
		for(i = 0; i < W; i++, k++)
		{
			YCASE[k] = j;
			XCASE[k] = i;
			MCASE[k] = 1l << i;
			NUMCASE[j][i] = k;
		}
	}
}

static void rotation(int y[5], int x[5])
{
	int i, j;

	for(j = 0; j < 5; j++)
	{
		i = y[j];
		y[j] = x[j];
		x[j] = -i;
	}

	i = x[0];
	for(j = 1; j < 5; j++) if(x[j] < i) i = x[j];
	for(j = 0; j < 5; j++) x[j] -= i;
}

static void retournerpiece(int x[5])
{
	int i, j;

	for(i = j = 0; j < 5; j++)
	{
		x[j] = -x[j];
		if(x[j] < i) i = x[j];
	}

	for(j = 0; j < 5; j++) x[j] -= i;
}

static void CalculPmInit(pentambase *pb, pm *pmi, int base)
{
	int k;

	for(k = 0; k < 5; k++)
	{
		if(pb->x[k] >= W)
		{
			pmi->base = -1;
			return;
		}
		if(pb->y[k] >= H)
		{
			pmi->base = -1;
			return;
		}
	}

	for(k = 0; k < HMAX; k++)
		pmi->l[k] = 0l;

	for(k = 0; k < 5; k++)
	{
		pmi->l[pb->y[k]] |= (1l << pb->x[k]);
		pmi->cases[k] = NUMCASE[pb->y[k]][pb->x[k]];
	}

	pmi->base = base;
}

static int ltcmp(long *l1, long *l2)
{
	int k;

	for(k = 0; k < H; k++)
	{
		if(l1[k] > l2[k]) return 1;
		if(l1[k] < l2[k]) return -1;
	}

	return 0;
}

static int trier8(pm *pmi)
{
	int k, n, j;

	for(j = k = 0; k < 8; k++)
		if(pmi[k].base >= 0)
			pmi[j++] = pmi[k];
	if(j == 0) return 0;

	qsort(pmi, j, sizeof(pm), (int (*)(const void *, const void *)) ltcmp);

	for(n = k = 1; k < j; k++)	/*	suppression des doublons */
		if(ltcmp(pmi[k].l, pmi[k - 1].l))
			pmi[n++] = pmi[k];

	return n;
}

static int CalculerInit(pm *pmi)
{
	int n, i, k;
	pentambase pb;

	for(n = k = 0; k < 12; k++)
	{
		pb = BASE[k];
		CalculPmInit(&pb, pmi + n, k);

		for(i = n + 1; i <= n + 3; i++)
		{
			rotation(pb.y, pb.x);
			CalculPmInit(&pb, pmi + i, k);
		}

		pb = BASE[k];
		retournerpiece(pb.x);
		CalculPmInit(&pb, pmi + n + 4, k);

		for(i = n + 5; i <= n + 7; i++)
		{
			rotation(pb.y, pb.x);
			CalculPmInit(&pb, pmi + i, k);
		}

		n += trier8(pmi + n);
	}

	return n;
}

static int translatepiece(pm *pmi, int j, int i, long *ll, pm *pmt)
{
	int k, t, c = 0;

	for(k = j; k < H; k++)
	{
		pmt->l[k] = pmi->l[k - j] << i;
		if(pmt->l[k])
		{
			if((pmt->l[k] & ll[k]) != pmt->l[k])
				return 0;
			for(t = i + 4; t >= i; t--)
				if(pmt->l[k] & (1l << t))
					pmt->cases[c++] = NUMCASE[k][t];
		}
	}
	for(k = 0; k < j; k++) pmt->l[k] = 0;

	pmt->base = pmi->base;
	return 1;
}

static int translation(int ninit, pm *pmi)
{
	int t, k, hp, wp, j, i;
	long ll[HMAX];

	for(k = 0; k < HMAX; k++) ll[k] = 0l;
	for(k = 0; k < S; k++) ll[YCASE[k]] |= (1l << XCASE[k]);

	for(t = k = 0; k < ninit; k++)
	{
		for(hp = H - 1; hp > 0; hp--)
			if(pmi[k].l[hp])
				break;

		wp = 0;
		for(i = 0; i < 5 && wp < 4; i++)
		{
			for(j = 4; j > wp; j--)
			{
				if(pmi[k].l[i] & (1l << j))
				{
					wp = j;
					break;
				}
			}
		}

		for(j = 0; j + hp < H; j++)
			for(i = 0; i + wp < W; i++)
				if(translatepiece(pmi + k, j, i, ll,
						TOUS + t)) t++;
	}

	return t;
}

static int graphselect(int avant)
{
	int k, t, apres;

	for(apres = k = 0; k < avant; k++)
	{
		for(t = 0; t < S; t++) GRAPHE[YCASE[t] * W + XCASE[t]] = 0;
		if(scangraphe(TOUS + k, 1)) TOUS[apres++] = TOUS[k];
	}

	return apres;
}

static int symetrique(int avant, int symhb, int symgd)
{
	int bx, by, k, apres, gauche, droite, haut, bas;
	int xg, xd, yh, yb, j;
	char c;

	if(symhb == 0 && symgd == 0) return avant;

	if(H & 1) c = LETTRESYMIMPAIR;
	else	c = LETTRESYMPAIR;
	for(by = 0; by < 12; by++)
		if(BASE[by].nom == c)
			break;

	if(W & 1) c = LETTRESYMIMPAIR;
	else	c = LETTRESYMPAIR;
	for(bx = 0; bx < 12; bx++)
		if(BASE[bx].nom == c)
			break;

	if(by == 12 || bx == 12) return 0;

	if(H & 1) yb = (yh = (H - 1) / 2) + 1;
	else	yb = yh = H / 2;
	if(W & 1) xd = (xg = (W - 1) / 2) + 1;
	else	xd = xg = W / 2;

	if(symhb == 0) by = -1;
	if(symgd == 0) bx = -1;

	for(apres = k = 0; k < avant; k++)
	{
		if(TOUS[k].base == by)
		{
			haut = bas = 0;

			for(j = 0; j < 5; j++)
			{
				int y = YCASE[TOUS[k].cases[j]];
				if(y < yh) haut++;
				if(y >= yb) bas++;
			}

			if(haut == bas) return 0;
			if(haut < bas) continue;
		}

		if(TOUS[k].base == bx)
		{
			gauche = droite = 0;

			for(j = 0; j < 5; j++)
			{
				int x = XCASE[TOUS[k].cases[j]];
				if(x < xg) gauche++;
				if(x >= xd) droite++;
			}

			if(gauche == droite) return 0;
			if(gauche < droite) continue;
		}

		TOUS[apres++] = TOUS[k];
	}

	return apres;
}

static void trouvesymetries(int *symhb, int *symgd)
{
	int i, j, k;

	*symhb = *symgd = 1;

	for(k = H - 1, j = 0; *symhb == 1 && j < H; j++, k--)
		for(i = 0; *symhb == 1 && i < W; i++)
			if(NUMCASE[j][i] < 0 && NUMCASE[k][i] >= 0)
				*symhb = 0;

	for(k = W - 1, i = 0; *symgd == 1 && i < W; i++, k--)
		for(j = 0; *symgd == 1 && j < H; j++)
			if(NUMCASE[j][i] < 0 && NUMCASE[j][k] >= 0)
				*symgd = 0;
}

/*************************************************************************
*
*		Section 8 : Recherche des solutions			*/

static int pentacase(int reste, int grnum, int niveau);

static int intersect(pm *pm1, pm *pm2, int hmin, int hmax)
{
	int k;
	for(k = hmin; k <= hmax; k++)
		if(pm1->l[k] & pm2->l[k])
			return 1;
	return 0;
}

static int pentasolution(int niveau)
{
	int k;
	pm *pmc;

	pmc = RESTE[niveau][0];

	if(SOL_TROUVEES == SOL_ALLOUEES)
	{
		int sl;
		resultat *rs;

		sl = SOL_ALLOUEES + ALLOCSOLUCES;
		rs = (resultat *) realloc(SOLUTIONS, sl * sizeof(resultat));
		if(rs == NULL)
		{
			fprintf(stderr, "Erreur: Memoire insuffisante\n");
			return 0;
		}

		SOL_ALLOUEES = sl;
		SOLUTIONS = rs;
	}

	for(k = 0; k < S; k++) SOLUTIONS[SOL_TROUVEES][k] = RES[k];
	for(k = 0; k < 5; k++)
		SOLUTIONS[SOL_TROUVEES][pmc->cases[k]] = BASE[pmc->base].nom;

	SOL_TROUVEES++;
	return 1;
}

static int mettrepiece(pm *pmc, int reste, int grnum, int niveau)
{
	int n, k, hmin, hmax, gr, trou, rs;

	trou = GRAPHE[YCASE[pmc->cases[0]] * W + XCASE[pmc->cases[0]]];
	gr = scangraphe(pmc, grnum);
	if(gr == 0) return 0;	/* region % 5 != 0 */

	for(hmin = 0; hmin < H - 1; hmin++)
		if(pmc->l[hmin])
			break;
	for(hmax = H - 1; hmax > 0; hmax--)
		if(pmc->l[hmax])
			break;

	for(rs = k = 0; k < reste; k++)
	{
		pm *pmt = RESTE[niveau][k];
		if(pmt->base != pmc->base)
			if(intersect(pmc, pmt, hmin, hmax) == 0)
				RESTE[niveau + 1][rs++] = pmt;
	}

	if(rs > 0)
	{
		for(k = 0; k < 5; k++)
			RES[pmc->cases[k]] = BASE[pmc->base].nom;

		n = pentacase(rs, gr, niveau + 1);

		for(k = 0; k < 5; k++)
			RES[pmc->cases[k]] = ' ';
	}
	else	n = 0;

	for(k = H * W - 1; k >= 0; k--)
		if(GRAPHE[k] >= grnum)
			GRAPHE[k] = trou;
	for(k = 0; k < 5; k++)
		GRAPHE[YCASE[pmc->cases[k]] * W + XCASE[pmc->cases[k]]]
					= trou;

	return n;
}

static void estimetemps(int t, int div)
{
	if(t)
	{
		if(t < 0 || div <= 0 || t > div) return;
		printf("%4.1f%% ", 100.0 * (double) t / (double) div);
	}
	else	printf("0%% ");
	fflush(stdout);
}

static int pentacase(int reste, int grnum, int niveau)
{
	int c, p, q, b, ccour, n, sr, et;
	pm *pmc;

	NOEUD++;
	if(niveau == 0) estimetemps(0, 0);

	for(sr = c = 0; c < S; c++)
		if(RES[c] == ' ')
			CASES[sr++] = c;

	if(sr == 5)
	{
		NOEUDFIN++;
		return pentasolution(niveau);
	}

	for(c = 0; c < sr; c++) CCOMPTE[CASES[c]] = 0;
	for(p = 0; p < 12; p++) PCOMPTE[p] = 0;

	for(p = 0; p < reste; p++)
	{
		pmc = RESTE[niveau][p];
		PCOMPTE[pmc->base]++;
		for(c = 0; c < 5; c++) CCOMPTE[pmc->cases[c]]++;
	}

	ccour = CASES[0];
	for(c = 1; c < sr; c++)
	{
		if(CCOMPTE[CASES[c]] == 0)
		{			/* une case vide ne peut */
			NOEUDECHEC++;	/* plus etre recouverte */
			return 0;
		}

		if(CCOMPTE[CASES[c]] < CCOMPTE[ccour])
			ccour = CASES[c];
	}

	et = CCOMPTE[ccour];
	q = 0;

	if(S == 60)
	{
		b = 12;

		for(p = 0; p < 12; p++)
		{
			if(PCOMPTE[p] > 0 && PCOMPTE[p] < et)
			{
				et = PCOMPTE[p];
				b = p;
			}
		}

		if(b < 12)	/* selection de la piece b */
		{
			NOEUDPIECE++;

			for(n = p = 0; p < reste; p++)
			{
				pmc = RESTE[niveau][p];
				if(pmc->base == b)
				{
					n += mettrepiece(pmc, reste, grnum, niveau);
					if(niveau == 0) estimetemps(++q, et);
				}
			}

			return n;
		}
	}

		/*	selection de la case ccour	*/

	NOEUDCASE++;

	for(n = p = 0; p < reste; p++)
	{
		pmc = RESTE[niveau][p];
		if(pmc->l[YCASE[ccour]] & MCASE[ccour])
		{
			n += mettrepiece(pmc, reste, grnum, niveau);
			if(niveau == 0) estimetemps(++q, et);
		}
	}

	return n;
}

/*************************************************************************
*
*		Section 9 : Post-traitement des problemes
*				symetriques incomplets			*/

static int triersol(char *r1, char *r2)
{
	int k;
	for(k = 0; k < S; k++)
	{
		if(r1[k] < r2[k]) return -1;
		if(r2[k] < r1[k]) return 1;
	}
	return 0;
}

static void changesol(resultat s, int symhb, int symgd)
{
	int k, i, j, t;
	resultat r[4];
	char tb[HMAX][WMAX];

	for(k = j = 0; j < H; j++)
		for(i = 0; i < W; i++)
			if(NUMCASE[j][i] < 0) tb[j][i] = '.';
			else	tb[j][i] = s[k++];

	for(k = 0; k < S; k++) r[0][k] = s[k];

	if(symhb && symgd)
	{
		for(k = 0; k < S; k++) r[1][k] = s[S - 1 - k];
		t = 2;
	}
	else	t = 1;

	if(symhb)
	{
		for(k = 0, j = H - 1; j >= 0; j--)
			for(i = 0; i < W; i++)
				if(tb[j][i] != '.') r[t][k++] = tb[j][i];

		t++;
	}

	if(symgd)
	{
		for(k = 0, j = 0; j < H; j++)
			for(i = W - 1; i >= 0; i--)
				if(tb[j][i] != '.') r[t][k++] = tb[j][i];

		t++;
	}

	qsort(r, t, sizeof(resultat),
			(int (*) (const void *s1, const void *s2)) triersol);
	for(k = 0; k < S; k++) s[k] = r[0][k];
}

static int soldifferent(resultat r, resultat s)
{
	int k;
	for(k = 0; k < S; k++)
		if(r[k] != s[k])
			return 1;
	return 0;
}

static void posttraitesym(int symhb, int symgd)
{
	int i, j, k, t;

	if(symhb == 0 && symgd == 0) return;

	for(j = 0; j < SOL_TROUVEES; j++)
		changesol(SOLUTIONS[j], symhb, symgd);
	qsort(SOLUTIONS, SOL_TROUVEES, sizeof(resultat),
			(int (*) (const void *s1, const void *s2)) triersol);

	for(i = j = 0; j < SOL_TROUVEES; i++)
	{
		for(k = 0; k < S; k++) SOLUTIONS[i][k] = SOLUTIONS[j][k];
		for(t = 1, j++; t < 4 && j < SOL_TROUVEES; j++, t++)
			if(soldifferent(SOLUTIONS[i], SOLUTIONS[j]))
				break;
	}

	SOL_TROUVEES = i;
}

/*************************************************************************
*
*		Section 10 : Main et entrees-sorties			*/

static int liredata(char *nom)
{
	int i, j;
	FILE *ff;
	char buf[256];

	for(j = 0; j < HMAX; j++)
		for(i = 0; i < WMAX; i++)
			NUMCASE[j][i] = -1;

	if(strcmp(nom, "-") == 0) ff = stdin;
	else	if((ff = fopen(nom, "rt")) == NULL) return -1;

	for(S = H = 0; H < HMAX; H++)
	{
		if(fscanf(ff, "%s", buf) != 1) break;

		if(H == 0)
		{
			W = (int) strlen(buf);
			if(W <= 0 || W > WMAX) break;
		}
		else	if(W != (int) strlen(buf)) break;

		for(i = 0; i < W; i++)
			if(buf[i] != '0' && buf[i] != '1')
				break;

		if(i < W) break;

		for(i = 0; i < W; i++)
		{
			if(buf[i] == '1')
			{
				XCASE[S] = i;
				YCASE[S] = H;
				NUMCASE[H][i] = S;
				MCASE[S] = 1l << i;
				S++;
			}
		}
	}

	if(ff != stdin) fclose(ff);
	if(H == 0 || H == HMAX || S == 0 || S > 60 || S % 5 != 0) return -2;

	return 0;
}

static void affichersolutions(double tcpu, char *titre)
{
	int k;

	printf("\n\n%%\n");
	printf("Temps %g\n", tcpu);
	printf("Hauteur %d\n", H);
	printf("Largeur %d\n", W);
	printf("Pieces %d\n", S / 5);
	printf("Solutions %d\n", SOL_TROUVEES);

	if(titre) printf("%s\n\n", titre);
	else	printf("%dx%d\n\n", H, W);

	for(k = 0; k < SOL_TROUVEES; k++)
	{
		int j, i, t;
		char ligne[WMAX + 1];

		printf("Solution %d\n", k + 1);
		ligne[W] = '\0';

		for(t = j = 0; j < H; j++)
		{
			for(i = 0; i < W; i++)
			{
				if(NUMCASE[j][i] < 0) ligne[i] = '.';
				else	ligne[i] = SOLUTIONS[k][t++];
			}
			puts(ligne);
		}
		puts("");
	}
}

static void syntaxe(char *nom)
{
	puts("syntaxe: il y a deux formes d'appel.");
	puts("\t- Soit on donne la hauteur et la largeur du rectangle");
	puts("\t- Soit on donne un nom de fichier (- pour stdin).");
	printf("-> %s 4 15\n", nom);
	printf("-> %s exemple1.txt\n", nom);
	puts("\tPour un rectangle les dimensions doivent verifier:");
	printf("\t\t0 < hauteur <= %d  et  0 <= largeur <= %d\n", HMAX, WMAX);
	puts("\tLa surface a remplir doit etre un multiple de 5");
	puts("\tstrictement positif et inferieur ou egal a 60.");
	puts("\tLe programme permet de traiter les problemes incomplets");
	puts("\tpour lesquels tous les pentaminos ne sont pas utilises :");
	printf("-> %s 3 5\n", nom);
	printf("-> %s exemple2.txt\n", nom);
	puts("\tLorsqu'on utilise un nom de fichier, celui-ci doit contenir");
	puts("\tdes valeurs ascii 0 ou 1 representant la forme a remplir.");
	puts("\tLes  symetries sont traitees au niveau de l'algorithme de");
	puts("\trecherche des solutions pour problemes complets (60 cases).");
	puts("\tUn post traitement est utilise pour problemes incomplets");
	puts("\tEnfin l'entree et la sortie standard peuvrent etre redirigee");
	puts("\tsur les programmes graphiques qui necessitent XWindow");
	puts("\tet les Widgets Athena. editpm peut prendre en entree un");
	puts("\tnom de fichier, et produit le fichier EDITPM.txt en sortie.");
	printf("-> %s exemple3.txt | voirpm\n", nom);
	printf("-> editpm | %s - | voirpm\n", nom);
	printf("-> editpm EDITPM.txt | %s - | voirpm\n", nom);
}

void main(int argc, char **argv)
{
	int k, ninit, tous, symhautbas, symgaudr;
	pm pminit[96];
	clock_t tm;
	double tcpu;

	tm = clock();

	if(argc != 2 && argc != 3)
	{
		syntaxe(argv[0]);
		return;
	}

	if(argc == 3)
	{
		H = atoi(argv[1]);
		W = atoi(argv[2]);

		if(H <= 0 || H > HMAX || W <= 0 || W > WMAX)
		{
			syntaxe(argv[0]);
			return;
		}

		S = W * H;
		if(S > 60 || (S % 5) != 0)
		{
			syntaxe(argv[0]);
			return;
		}

		initrectcases();
	}
	else
	{
		if(liredata(argv[1]) < 0)
		{
			fprintf(stderr, "Erreur lecture : %s\n", argv[1]);
			return;
		}
	}
	fprintf(stderr, "Rectangle = %d x %d -> %d pentaminos\n", H, W, S / 5);

	ninit = CalculerInit(pminit);
	fprintf(stderr, "Init = %d pieces\n", ninit);
	tous = translation(ninit, pminit);
	fprintf(stderr, "Total = %d pieces\n", tous);

	if(S < H * W)
		for(k = H * W - 1; k >= 0; k--)
			GRAPHE[k] = -3;
	tous = graphselect(tous);
	fprintf(stderr, "Total apres graphselect = %d pieces\n", tous);

	if(S == W * H)	/* rectangle */
	{
		symhautbas = symgaudr = 1;
		tous = symetrique(tous, 1, 1);
		fprintf(stderr, "Total apres symetrique = %d pieces\n", tous);
		if(S == 60) fprintf(stderr, "Probleme rectangle complet\n");
		else	fprintf(stderr, "Probleme rectangle incomplet\n");
	}
	else
	{
		trouvesymetries(&symhautbas, &symgaudr);
		tous = symetrique(tous, symhautbas, symgaudr);
		fprintf(stderr, "Probleme non rectangle\n");
		if(symhautbas) fprintf(stderr, "Symetrie haut-bas\n");
		if(symgaudr) fprintf(stderr, "Symetrie gauche-droite\n");
		if(symhautbas == 0 && symgaudr == 0)
			fprintf(stderr, "Pas de symetrie\n");
	}

	if(tous == 0)
	{
		fprintf(stderr, "Erreur: pas de piece !\n");
		return;
	}

	for(k = 0; k < 12; k++)
	{
		if((RESTE[k] = (pm **) calloc(tous, sizeof(pm *))) == NULL)
		{
			for(k--; k >= 0; k--) free(RESTE[k]);
			fprintf(stderr, "Pas assez de memoire !\n");
			return;
		}
	}
	for(k = 0; k < tous; k++) RESTE[0][k] = TOUS + k;

	for(k = 0; k < S; k++)
	{
		CASES[k] = k;
		RES[k] = ' ';
		GRAPHE[YCASE[k] * W + XCASE[k]] = 0;
	}

	SOLUTIONS = NULL;
	SOL_ALLOUEES = SOL_TROUVEES = 0;
	NOEUD = NOEUDPIECE = NOEUDCASE = NOEUDECHEC = NOEUDFIN = 0;

	pentacase(tous, 1, 0);

	for(k = 11; k >= 0; k--) free(RESTE[k]);

	if(S < 60) posttraitesym(symhautbas, symgaudr);

	tcpu = (double) (clock() - tm) / (double) CLOCKS_PER_SEC;

	affichersolutions(tcpu, S == W * H ? NULL : argv[1]);

	if(SOLUTIONS) free(SOLUTIONS);

	fprintf(stderr, "Solutions = %d\n", SOL_TROUVEES);
	fprintf(stderr, "Noeuds = %d (p = %d, c = %d, e = %d, f = %d)\n",
			NOEUD, NOEUDPIECE, NOEUDCASE, NOEUDECHEC, NOEUDFIN);

	fprintf(stderr, "Temps CPU apres affichage = %g s.\n",
			(double) (clock() - tm) / (double) CLOCKS_PER_SEC);
}