Untitled

// Modified output and added Timer() code#include <ctime>#include <iostream>#include <string>#include <cstdlib>#define DISPLAY_RESULTS 0#define CX 5#define CY 5#define N 5long time1;typedef struct {			int x [10];			int y [10];			int sx, sy;			int y0;		}			PAT;typedef struct	{			PAT pats [8];			int n;			char c;			int used;		}			FIG;#define SX 10#define SY 6char field [SY+2][SX+2] = {0};char testfield [SY+2][SX+2];FIG figs [20];int nfigs;char figdef [] =	"I*****;"	"L****/*;"	"Y****/.*;"	"V***/*/*;"	"P***/**;"	"U***/*.*;"	"T***/.*/.*;"	"N***/..**;"	"Z**/.*/.**;"	"R**/.**/.*;"	"W**/.**/..*;"	"X.*/***/.*;";//char rules [8][4] = {char rules [8][5] = {	"+X+Y",	"-Y+X",	"-X-Y",	"+Y-X",	"-X+Y",	"-Y-X",	"+X-Y",	"+Y+X"	};int	equpat (PAT * p, PAT * q){	int i, j;	for (i = 0; i < N; i++)	{		for (j = 0; j < N; j++)			if (p->x[i] == q->x[j] && p->y[i] == q->y[j])				break;		if (j == N)			return 0;		}	return 1;}void	normalize_pat (PAT * p){	int xmin, xmax, ymin, ymax, i;	xmin = CX;	ymin = CY;	xmax = ymax = -1;	for (i = 0; i < N; i++)	{		if (p->x[i] < xmin) xmin = p->x[i];		if (p->x[i] > xmax) xmax = p->x[i];		if (p->y[i] < ymin) ymin = p->y[i];		if (p->y[i] > ymax) ymax = p->y[i];	}	p -> sx = xmax - xmin + 1;	p -> sy = ymax - ymin + 1;	p->y0 = CY;	for (i = 0; i < N; i++)	{		p->x[i] -= xmin;		p->y[i] -= ymin;		if (p->x[i] == 0 && p->y[i] < p->y0) p->y0 = p->y[i];	}}void	makeimages (FIG * f){	int i, j, k, x, y, X, Y;	normalize_pat (&f->pats [0]);	j = 1;	for (i = 1; i < 8; i++)	{		f->pats [j].sx = CX;		f->pats [j].sy = CY;		for (k = 0; k < N; k++)	{			x = f->pats[0].x[k];			y = f->pats[0].y[k];			X = rules [i][1] == 'X' ? x : y;			Y = rules [i][3] == 'X' ? x : y;			if (rules [i][0] == '-') X = CX - X - 1;			if (rules [i][2] == '-') Y = CY - Y - 1;			f->pats [j].x[k] = X;			f->pats [j].y[k] = Y;		}		normalize_pat (&f->pats [j]);		for (k = 0; k < j; k++)			if (equpat (&f->pats [k], &f->pats [j]))				break;		if (k == j) ++ j;	}	f->n = j;}char * readpat (PAT * p, char * s){	int x, y, mx, n;	x = y = mx = 0;	n = 0;	while (*s && *s != ';')	{		if (*s == '/')	{			++ y;			if (x > mx) mx = x;			x = 0;		} else	{			if (*s == '*')	{				p->x[n] = x;				p->y[n] = y;				++n;			}			++x;		}		++ s;	}	if (x > mx) mx = x;	p->sx = mx;	p->sy = y+1;	if (*s) ++ s;	if (n != N)		exit (1);	return s;}char * 	makefig (FIG * f, char * s){	f->c = *s++;	s = readpat (&f->pats [0], s);	makeimages (f);	return s;}void makefigs (void){	int	i;	char * s = figdef;	for (i = 0; i < sizeof (figs)/sizeof (FIG) && *s; i++)		s = makefig (&figs [i], s);	nfigs = i;}/* --------------------------------------------------- */int	nsols = 0;#if DISPLAY_RESULTSvoid	disp (void){	int y, x;	++nsols;	printf ("============== Solution #%d: =============== \n", nsols);	for (y = 1; y <= SY; y++)	{		for (x = 1; x <= SX; x++)			putchar (field [y][x] ? field [y][x] : '.');		printf ("\n");	}	printf ("\n");}#elsevoid	disp (void){	++nsols;}#endifvoid	put_fig (PAT * p, int x, int y, char c){	int i;	for (i = 0; i < N; i++)		field [y+p->y[i]][x+p->x[i]] = c;}int	find_hole (int x0, int* xstart, int* ystart){	int x, y, n;	for (x = x0; x <= SX; x ++)		for (y = 1; y <= SY; y++)			if (!field [y][x])	{				*xstart = x;				*ystart = y;				return 1;			}	return 0;}void	deep (int d, int x0);void	try_put (PAT * p, char c, int d, int x, int y){	int i;		y -= p->y0;	if (y < 1 || x + p->sx > SX+1 || y + p->sy > SY+1) return;	for (i = 0; i < N; i++)		if (field [y+p->y[i]][x+p->x[i]])			return;	put_fig (p, x, y, c);	if (d == 1)		disp ();	else		deep (d-1, x);	put_fig (p, x, y, 0);}void	deep (int d, int x0){	int i, j, x, y;	if (! find_hole (x0, &x, &y))		return;	for (i = 0; i < nfigs; i++)		if (! figs [i].used)	{			figs [i].used = 1;			for (j = 0; j < figs [i].n; j++)				try_put (&figs [i].pats [j], figs [i].c, d, x, y);			figs [i].used = 0;		}}void	search (void){	int i, j;	for (i = 0; i < nfigs; i++) figs [i].used = 0;	for (i = 0; i < SX+2; i++)		field [0][i] = field [SY+1][i] = '*';	for (i = 0; i < SY+2; i++)		field [i][0] = field [i][SX+1] = '*';	for (i = 0; i < nfigs; i++)	{		figs [i].used = 1;		for (j = 0; j < figs [i].n; j++)			if (figs [i].pats [j].sx <= SX &&			    figs [i].pats [j].sy <= SY)			{			//	printf (" %d. %d\n", i, j);				put_fig (&figs [i].pats [j], 1, 1, figs [i].c);				deep (nfigs-1, 1);				put_fig (&figs [i].pats [j], 1, 1, 0);			}		figs [i].used = 0;	}}#ifdef __linux__int main ()#elseint _cdecl main (void)#endif{    clock_t start=clock();	makefigs ();	search ();	clock_t endt=clock(); 	std::cout << nsols << std::endl;	std::cout <<"Time: " << double(endt-start)/CLOCKS_PER_SEC * 1000 << " ms\n"; 	return 0;}