イラストロジック解法プログラム

/*		illust.cpp		*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#include <graphics.h>

#define		SETCHECK		/* set1(), set0() on		*/

typedef		char *		pchar;
typedef		int *		pint;

/*   data print out flag		   routine or process */
/*#define		TEST			/* test mode				*/
/*#define		DEBUG			/* main						*/
/*#define		DEBUG1			/* runcheck process			*/
/*#define		DEBUG2			/* runcheck					*/
/*#define		DEBUG4			/* shrinkmask				*/
/*#define		DEBUG6			/* allcheck (detail)		*/
/*#define		DEBUG11			/* run10					*/
/*#define		DEBUG13			/* allcheck					*/

const int buf_size = 256;

void wait(char *message);
void error(void);
void usage(char *s);
void monx(char *mask);
void mony(char *mask);
void getdata(int **run, int *n, FILE *fin);
void memover(void);
void matprint(int *mat, int n, char *title);
int checkmask(char *mask);
int calrest(int *run, int m, int n);
void memset_allcheck(int m);
void memfree_allcheck(void);
void allcheck(int *run, char *mask, int m, int n);
void rest0(int *run, char *mask, int n);
int inccheck(int *sp, int n);
int incsp1(int *sp, int totalsp, int n, int i);
char *newchar(int n);
int *newint(int n);
int **newpint(int n);
char **newpchar(int n);
void runcheck(int *run, char *mask, int m, int n);
void run10(int *run, char *mask, int m, int n);
void shrinkmask(int *run, char *mask, int m, int n,
	int *newrun, char *newmask, int *set, int *mm, int *nn);
void remake(char *mask, char *mask1, int *set, int m);
int leftfind(char *mask, char *pattern);

#ifdef SETCHECK
void set1(char *mask);
void set0(char *mask);
#endif

char title[40];
char *buf;
int *tmp;
int *xx, *yy, xms, yms;
int errflag = 1, errset = 0;

int main(int argc, char *argv[])
{
#ifdef TEST
	int runf[20] =
		{2, 8, 6, 12, 10, 15, 2};
	char maskf[100] =
		"....011111111011111100111111111111..11111111..0111111111111111011";
	int mf = 65, nf = 7;

	memset_allcheck(mf);
	allcheck(runf, maskf, mf, nf);
	printf("maskf=%s\n", maskf);
	exit(0);
#endif

	int i, j, k;
	int cflag = 0, dflag = 0, gflag = 1, lflag = 0, mflag = 0, pflag = 0;
	int rflag = 1, tflag = 0, wflag = 0;

	if(argc < 2)	usage(argv[0]);

	k = 1;
	while(*(argv[k]) == '-')
	{
		char *p = argv[k] + 1;
		while(*p)
		{
			if(*p == 'p')	pflag = 1;
			else if(*p == 'c')	cflag = 1;
			else if(*p == 't')	tflag = 1;
			else if(*p == 'l')	lflag = 1;
			else if(*p == 'g')	gflag = 0;
			else if(*p == 'm')	mflag = 1;
			else if(*p == 'w')	wflag = 1;
			else if(*p == 'r')	rflag = 0;
			else if(*p == 'd')	dflag = 1;
			else
			{
				fprintf(stderr, "Illegal option !!\n");
				usage(argv[0]);
			}
			p++;
		}
		k++;
	}

	buf = newchar(buf_size);

	FILE *fin = fopen(argv[k], "rt");
	if(fin == NULL)
	{
		strcpy(buf, argv[k]);
		strcat(buf, ".ill");
		fin = fopen(buf, "rt");
		if(fin == NULL)
		{
			fprintf(stderr, "Error : file(%s) can't open.\n", argv[k]);
			exit(-1);
		}
	}

	FILE *fdata;
	if(dflag)
	{
		char *p = strchr(argv[k], '.');
		if(p != argv[k]) *p = '\0';
		strcpy(buf, argv[k]);
		strcat(buf, ".dat");
		fdata = fopen(buf, "r");
		if(fdata != NULL)
		{
			fprintf(stderr, "Error : file(%s) is already exist.\n", buf);
			exit(-1);
		}
		fdata = fopen(buf, "wt");
	}

	fgets(title, 40, fin);
	int M = atoi(title);			/* 横升目数 */
	if(M == 0)
	{
		title[strlen(title) - 1] = '\0';
		fgets(buf, buf_size, fin);
		M = atoi(buf);
	}
	else title[0] = '\0';

	fgets(buf, buf_size, fin);
	int N = atoi(buf);			/* 縦升目数 */

	if(cflag)
	{
		i = M;
		M = N;
		N = i;
	}

	int m = (M >= N)? M: N;

	int *xn = newint(M);
	int *yn = newint(N);
	int **xrun = newpint(M);
	int **yrun = newpint(N);

	tmp = newint(m / 2 + 1);
	if(cflag)
	{
		for(i = 0; i < N; i++)	getdata(yrun + i, yn + i, fin);
		for(i = 0; i < M; i++)	getdata(xrun + i, xn + i, fin);
	}
	else
	{
		for(i = 0; i < M; i++)	getdata(xrun + i, xn + i, fin);
		for(i = 0; i < N; i++)	getdata(yrun + i, yn + i, fin);
	}
	delete tmp;

	fclose(fin);
	delete buf;

	if(pflag)
	{
		for(i = 0; i < M; i++)
		{
			printf("< x run %3d >", i);
			matprint(xrun[i], xn[i], "");
		}
		for(i = 0; i < N; i++)
		{
			printf("< y run %3d >", i);
			matprint(yrun[i], yn[i], "");
		}
		putchar('\n');
	}
								/* チェックサム */
	int sum = 0;
	for(i = 0; i < M; i++)	for(j = xn[i] - 1; j >= 0;)	sum += xrun[i][j--];
	for(i = 0; i < N; i++)	for(j = yn[i] - 1; j >= 0;)	sum -= yrun[i][j--];
	if(sum)
	{
		fprintf(stderr, "チェックサムエラー  sum=%d\n", sum);
		exit(-3);
	}

	if(lflag)
	{
		int *pw, **ps = xrun, **pe = xrun + M - 1;
		while(ps < pe)
		{
			pw = *ps;
			*ps++ = *pe;
			*pe-- = pw;
		}
		i = 0;
		j = M - 1;
		while(i < j)
		{
			k = xn[i];
			xn[i++] = xn[j];
			xn[j--] = k;
		}
		for(i = 0; i < N; i++)
		{
			if(yn[i] < 2)	continue;
			j = 0;
			k = yn[i] - 1;
			while(j < k)
			{
				int w = yrun[i][j];
				yrun[i][j++] = yrun[i][k];
				yrun[i][k--] = w;
			}
		}
	}

	if(tflag)
	{
		int *pw, **ps = yrun, **pe = yrun + N - 1;
		while(ps < pe)
		{
			pw = *ps;
			*ps++ = *pe;
			*pe-- = pw;
		}
		i = 0;
		j = N - 1;
		while(i < j)
		{
			k = yn[i];
			yn[i++] = yn[j];
			yn[j--] = k;
		}
		for(i = 0; i < M; i++)
		{
			if(xn[i] < 2)	continue;
			j = 0;
			k = xn[i] - 1;
			while(j < k)
			{
				int w = xrun[i][j];
				xrun[i][j++] = xrun[i][k];
				xrun[i][k--] = w;
			}
		}
	}

	char **mat_mask = newpchar(M);

	char *mask = newchar(m);
	int *xchange = newint(N);
	int *ychange = newint(M);

	for(i = M - 1; i >= 0;)
	{
		char *p = mat_mask[i--] = newchar(N);
		j = N;
		while(j--)	*p++ = '.';
		*p = '\0';
	}

#ifdef DEBUG
	printf("No.: xn : xrun\n");
	for(j = 0; j < M; j++)
	{
		printf("%2d : %2d", j, xn[j]);
		matprint(xrun[j], xn[j], "");
	}
	printf("No.: yn : yrun\n");
	for(j = 0; j < N; j++)
	{
		printf("%2d : %2d", j, yn[j]);
		matprint(yrun[j], yn[j], "");
	}
#endif

	int x, y, xm, ym, xmm, ymm, step;

	int gdriver = PC98, gmode = PC98C16;
	initgraph(&gdriver, &gmode, "");

	int ecode = graphresult();
	if(ecode != grOk)
	{
		fprintf(stderr , "Error : Graphics cannot initialize\n");
		fprintf(stderr , "   error message [ %s ]\n", grapherrormsg(ecode));
		exit(1);
	}

	if(gflag)
	{
		step = 627 / (M + 1);
		if(step > 371 / (N + 1))	step = 371 / (N + 1);
		int step5 = step * 5;

		xx = newint(M);
		yy = newint(N);
		for(i = 0, x = step / 2; i < M; i++, x += step)	xx[i] = x;
		for(i = 0, y = step / 2; i < N; i++, y += step)	yy[i] = y;

		xm = step * M;
		ym = step * N;

		setcolor(WHITE);
		setlinestyle(SOLID_LINE, 0, NORM_WIDTH);

		for(x = xm; x >= 0; x -= step)	line(x, 0, x, ym);
		for(y = ym; y >= 0; y -= step)	line(0, y, xm, y);
		for(x = 1; x <= xm + 1; x += step5)	line(x, 0, x, ym + 1);
		for(y = 1; y <= ym + 1; y += step5)	line(0, y, xm + 1, y);

		xm += 6;
		ym += 6;

		if(mflag)
		{
			if((xmm = xm + step + 6) > 639)	xmm = 639;
			if((ymm = ym + step + 6) > 383)	xmm = 383;

			for(x = step * M; x >= 0; x -= step)
				line(x, ymm - step, x, ymm);
			for(x = step * M + 1; x >= 1; x -= step5)
				line(x, ymm - step, x, ymm);
			line(0, ymm - step, step * M, ymm - step);
			line(0, ymm, step * M, ymm);

			for(y = step * N; y >= 0; y -= step)
				line(xmm - step, y, xmm, y);
			for(y = step * N + 1; y >= 1; y -= step5)
				line(xmm - step, y, xmm, y);
			line(xmm - step, 0, xmm - step, step * N);
			line(xmm, 0, xmm, step * N);
			xms = xmm - step / 2;
			yms = ymm - step / 2;

			setfillstyle(SOLID_FILL, WHITE);
		}
	}

	memset_allcheck(m);

	char *monmask;
	if(gflag && wflag)	monmask = newchar(m);

	char *pcc, **smask;
	int icc, ncc = 0;
	long count = 0;
	for(i = M - 1; i >= 0;)	ychange[i--] = 1;

	for(int firstflag = 1; ; firstflag = 0)
	{
		int contflag = 0;

		for(j = 0; j < M; j++)
		{
			if(ychange[j] == 0)	continue;
			count++;
			if(gflag)
			{
				x = xx[j];
				setcolor(WHITE);
				circle(x, ym, 4);
			}
			strcpy(mask, mat_mask[j]);
#ifdef DEBUG
			printf("\n<xcheck in of %2d> ", j);
			matprint(xrun[j], xn[j], "run");
#endif
			if(mflag)
			{
				gotoxy(1, 25);
				clreol();
				for(i = 0; i < xn[j];)	cprintf("%d ", xrun[j][i++]);
				if(gflag == 0)
				{
					gotoxy(1, 24);
					clreol();
					cprintf("%s", mask);
				}
				else if(wflag)	strcpy(monmask, mask);
				else	monx(mask);
			}
			if(pflag)	printf("x%3d in  : %s\n", j, mask);
			allcheck(xrun[j], mask, N, xn[j]);
			if(pflag)	printf("     out : %s\n", mask);

			if(gflag && rflag)
			{
				if(wflag)
				{
					if(mflag)	monx(monmask);
					wait("Do it yourself!");
				}
				for(i = 0; i < N; i++)
				{
					if(mat_mask[j][i] != (k = mask[i]))
					{
						mat_mask[j][i] = xchange[i] = contflag = k;
						if(k == '1')	setfillstyle(SOLID_FILL, YELLOW);
						else			setfillstyle(CLOSE_DOT_FILL, YELLOW);
						floodfill(x, yy[i], WHITE);
					}
				}
				if(mflag)	monx(mask);
			}
			else
			{
				for(i = 0; i < N; i++)
					if(mat_mask[j][i] != mask[i])
						mat_mask[j][i] = xchange[i] = contflag = mask[i];
			}
			if(gflag)
			{
				setcolor(BLACK);
				circle(x, ym, 4);
			}
			if(wflag)	wait("Hit any key!!");
		}
		if(firstflag)	for(i = N - 1; i >= 0;)	xchange[i--] = 1;
		for(i = M - 1; i >= 0;)	ychange[i--] = 0;

		for(j = 0; j < N; j++)
		{
			if(xchange[j] == 0)	continue;
			count++;
			if(gflag)
			{
				y = yy[j];
				setcolor(WHITE);
				circle(xm, y, 4);
			}
			for(i = 0; i < M; i++)	mask[i] = mat_mask[i][j];
			mask[M] = '\0';
#ifdef DEBUG
			printf("\n<ycheck in of %2d> ", j);
			matprint(yrun[j], yn[j], "run");
#endif
			if(mflag)
			{
				gotoxy(1, 25);
				clreol();
				for(i = 0; i < yn[j];)	cprintf("%d ", yrun[j][i++]);
				if(gflag == 0)
				{
					gotoxy(1, 24);
					clreol();
					cprintf("%s", mask);
				}
				else if(wflag)	strcpy(monmask, mask);
				else	mony(mask);
			}
			if(pflag)	printf("y%3d in  : %s\n", j, mask);
			allcheck(yrun[j], mask, M, yn[j]);
			if(pflag)	printf("     out : %s\n", mask);

			if(gflag && rflag)
			{
				if(wflag)
				{
					if(mflag)	mony(monmask);
					wait("Do it yourself!");
				}
				for(i = 0; i < M; i++)
				{
					if(mat_mask[i][j] != (k = mask[i]))
					{
						mat_mask[i][j] = ychange[i] = contflag = k;
						if(k == '1')	setfillstyle(SOLID_FILL, YELLOW);
						else			setfillstyle(CLOSE_DOT_FILL, YELLOW);
						floodfill(xx[i], y, WHITE);
					}
				}
				if(mflag)	mony(mask);
			}
			else
			{
				for(i = 0; i < M; i++)
					if(mat_mask[i][j] != mask[i])
						mat_mask[i][j] = ychange[i] = contflag = mask[i];
			}
			if(gflag)
			{
				setcolor(BLACK);
				circle(xm, y, 4);
			}
			if(wflag)	wait("Hit any key!!");
		}
errloop:
		if(errflag && contflag == 0)
		{
			for(i = 0; i < M; i++)	if(strchr(mat_mask[i], '.'))	break;
			if(i == M)	break;
			icc = i;
			errflag = errset = 0;
			smask = newpchar(M);
			for(i = 0; i < M; i++)
			{
				smask[i] = newchar(N);
				strcpy(smask[i], mat_mask[i]);
			}
		}
		if(errflag == 0)
		{
			if(ncc == 0)
			{
				ncc = 1;
				pcc = strchr(mat_mask[icc], '.');
				*pcc = ychange[icc] = '1';
				setfillstyle(SOLID_FILL, YELLOW);
				floodfill(xx[icc], yy[pcc - mat_mask[icc]], WHITE);
			}
			else
			{
				if(errset == 1)
				{
					for(i = 0; i < M; i++)	strcpy(mat_mask[i], smask[i]);
					*pcc = ychange[icc] = '0';
					errset = 0;
					setfillstyle(CLOSE_DOT_FILL, YELLOW);
					floodfill(xx[icc], yy[pcc - mat_mask[icc]], WHITE);
				}
				else if(contflag == 0)
				{
					ncc = 0;
					errflag = 1;
					goto errloop;
				}
			}
		}
		for(i = N - 1; i >= 0;)	xchange[i--] = 0;
	}

	memfree_allcheck();

	if(rflag == 0)
	{
		for(i = 0; i < M; i++)
		{
			char *p = mat_mask[i];
			j = 0;
			while(*p)
			{
				if(*p++ == '1')	setfillstyle(SOLID_FILL, YELLOW);
				else			setfillstyle(CLOSE_DOT_FILL, YELLOW);
				floodfill(xx[i], yy[j++], WHITE);
			}
		}
	}

	if(mflag && gflag)
	{
		setviewport(0, ymm - step, step * M + 1, ymm, 1);
		clearviewport();
		setviewport(xmm - step, 0, xmm, step * N + 1, 1);
		clearviewport();
	}

	gotoxy(1, 24);
	clreol();
	gotoxy(1, 25);
	clreol();

	fprintf(stderr, "Complete !  Cycle = %ld", count);
	if(title[0] != '\0')	fprintf(stderr, "  Title:%s", title);

	if(dflag)
	{
		fprintf(fdata, "%s\n%d\n%d\n", title, M, N);
		for(i = 0; i < M; i++)	fprintf(fdata, "%s\n", mat_mask[i]);
		fclose(fdata);
		fprintf(stderr, "\nData output complete.");
	}
	return 0;
}

void wait(char *message)
{
	int x = 80 - strlen(message);
	gotoxy(x, 25);
	clreol();
	fprintf(stderr, "%s", message);
	while(!kbhit())	;
	getch();
	gotoxy(x, 25);
	clreol();
}

void error(void)
{
	if(errflag)
	{
		fprintf(stderr, "Error : Illegal data. Cannot make up puzzle.\n");
		exit(-1);
	}
	errset = 1;
}

void usage(char *s)
{
	fprintf(stderr, "Usage : %s  [ -pctlgmwrd ]  < .ill file name >\n", s);
	fprintf(stderr, "        -p : Print data flag\n");
	fprintf(stderr, "        -c : Change axis flag\n");
	fprintf(stderr, "        -t : change Top to bottom flag\n");
	fprintf(stderr, "        -l : change Left to right flag\n");
	fprintf(stderr, "        -g : Graphics off flag\n");
	fprintf(stderr, "        -m : Monitor flag\n");
	fprintf(stderr, "        -w : Wait mode(Press any key when continue)\n");
	fprintf(stderr, "        -r : Result only\n");
	fprintf(stderr, "        -d : Data set flag\n");
	exit(0);
}

int style[4] = {SOLID_FILL, SOLID_FILL, CLOSE_DOT_FILL, SOLID_FILL};
int color[4] = {BLACK, YELLOW, YELLOW, YELLOW};

void monx(char *mask)
{
	char *p = mask;
	int *q = yy;
	while(*p)
	{
		int c = *p++ - '.';
		setfillstyle(style[c], color[c]);
		floodfill(xms, *q++, WHITE);
	}
	setfillstyle(SOLID_FILL, WHITE);
}

void mony(char *mask)
{
	char *p = mask;
	int *q = xx;
	while(*p)
	{
		int c = *p++ - '.';
		setfillstyle(style[c], color[c]);
		floodfill(*q++, yms, WHITE);
	}
	setfillstyle(SOLID_FILL, WHITE);
}

void getdata(int **run, int *n, FILE *fin)
{
	fgets(buf, buf_size, fin);
	char *p = buf;
	*n = 0;
	int j = 0;
	for(;;)
	{
		if((tmp[j++] = atoi(p++)) == 0)	break;
		(*n)++;
		do
		{
			if(*p == '\n' || *p == '\0')
			{
				if((*run = newint(*n)) == NULL)	return;
				for(j = 0; j < *n; j++)	*(*run + j) = tmp[j];
				return;
			}
		} while(*p++ != ' ');
		while(*p == ' ')	p++;
	}
}

void memover(void)
{
	fprintf(stderr, "Error : out of memory.\n");
	exit(-2);
}

void matprint(int *mat, int n, char *header)
{
	printf("%s : ", header);
	int *p = mat;
	while(n--)	printf("%2d ", *p++);
	putchar('\n');
}

int checkmask(char *mask)
{
	char *p = mask;
	while(*p)	if(*p++ == '.')	return 0;
	return 1;
}

#ifdef SETCHECK
void set1(char *mask)
{
	if(*mask == '0')	error();
	*mask = '1';
}

void set0(char *mask)
{
	if(*mask == '1')	error();
	*mask = '0';
}
#endif

int calrest(int *run, int m, int n)
{
	int rest = m - n + 1;
	while(n--)	rest -= run[n];
	return (rest >= 0)? rest: -1;
}

int *runs, *sets, *sp, *srun, *codein, *fix;
char *masks, *masks1, *masks2, *xelement, *code, *zero;

void memset_allcheck(int m)
{
	sets   = newint(m);
	codein = newint(m);
	fix    = newint(m);

	masks    = newchar(m);
	masks1   = newchar(m);
	masks2   = newchar(m);
	xelement = newchar(m);
	code     = newchar(m);
	zero     = newchar(m);

	m /= 2;
	runs = newint(m++);
	sp   = newint(m);
	srun = newint(m);
}

void memfree_allcheck(void)
{
	delete runs;
	delete sets;
	delete codein;
	delete fix;
	delete sp;
	delete srun;

	delete masks;
	delete masks1;
	delete masks2;
	delete xelement;
	delete code;
	delete zero;
}

void allcheck(int *run1, char *mask1, int mm, int nn)
{
	if(errflag == 0 && errset == 1)	return;
	int i, j, k, m, n;

#ifdef DEBUG13
	long count = 0;
	printf("< allcheck in >  m=%d, n=%d\n", mm, nn);
	printf("mask : %s\n", mask1);
	matprint(run1, nn, "run");
#endif

	if(nn == 0)
	{
		char *p = mask1;
		while(*p)	*p++ = '0';
#ifdef DEBUG13
		printf("< allcheck out >\nmask : %s\n", mask1);
#endif
		return;
	}

	if(checkmask(mask1))
	{
#ifdef DEBUG13
		printf("< allcheck out >\nmask : %s\n", mask1);
#endif
		return;
	}

	do
	{
		strcpy(masks1, mask1);
		runcheck(run1, mask1, mm, nn);
	} while(strcmp(masks1, mask1));

	for(;;)
	{
		shrinkmask(run1, mask1, mm, nn, runs, masks, sets, &m, &n);
		strcpy(masks1, masks);
		do
		{
			strcpy(masks2, masks);
			runcheck(runs, masks, m, n);
		} while(strcmp(masks2, masks));
		if(strcmp(masks1, masks) == 0)	break;
		remake(mask1, masks, sets, m);
	}
/*
	runcheck(run1, mask1, mm, nn);
	for(;;)
	{
		shrinkmask(run1, mask1, mm, nn, runs, masks, sets, &m, &n);
		strcpy(masks1, masks);
		runcheck(runs, masks, m, n);
		if(strcmp(masks1, masks) == 0)	break;
		remake(mask1, masks, sets, m);
	}
*/
	if(checkmask(masks))
	{
		remake(mask1, masks, sets, m);
#ifdef DEBUG13
		printf("< allcheck out >\nmask : %s\n", mask1);
#endif
		return;
	}

	int sp0 = 0;
	for(i = 0; i < runs[0]; i++)	if(masks[i] == '0')	break;
	if(i < runs[0])
	{
		sp0 += (i + 1);
		while(masks[++i] == '0')	sp0++;
	}

	int rest = calrest(runs, m, n);

	if(sp0 > rest)
	{
		remake(mask1, masks, sets, m);
#ifdef DEBUG13
		printf("< allcheck out >\nmask : %s\n", mask1);
#endif
		return;
	}

	int m1 = m - 1,	n1 = n - 1;

	xelement[m] = code[0] = code[m] = zero[m] = '\0';

	srun[0] = 0;
	for(i = 1; i <= n; i++)	srun[i] = srun[i - 1] + runs[i - 1];

	int nfix = 0, ncode = 0;
	for(i = 0; i < m; i++)
	{
		zero[i] = '0';
		if(masks[i] != '.')	fix[nfix++] = i;
		else	codein[ncode++] = i;
	}
	int startfix = 0;
	int lastcode = codein[ncode - 1];

#ifdef DEBUG6
	printf("mask : %s\n\nnfix = %d, ncode = %d\n", masks, nfix, ncode);
	matprint(fix, nfix, "fix");
	matprint(codein, ncode, "codein");
#endif

	sp[0] = sp0;
	sp[n] = rest - sp0;
	int totalsp = rest + n - 1;
	for(i = 1; i < n; i++)	sp[i] = 1;

#ifdef DEBUG6
	matprint(sp, n + 1, "sp");
	printf("totalsp = %d\n");
#endif

	int flag = 0;

	for(;;)
	{
#ifdef DEBUG13
		count++;
#endif
		strcpy(xelement, zero);
		char *p = xelement;
		for(i = 0; i < n;)
		{
			p += sp[i];
			k = runs[i++];
			while(k--)	*p++ = '1';
		}

		int unmatch = m;
		for(i = startfix; i < nfix;)
		{
			j = fix[i++];
			if(masks[j] != xelement[j])
			{
				unmatch = j;
				break;
			}
		}

#ifdef DEBUG6
		matprint(sp, n + 1, "sp");
		printf("mask     : %s\n", masks);
		printf("xelement : %s    unmatch=%d\n", xelement, unmatch);
#endif

		if(unmatch == m)
		{
			if(flag == 0)
			{
				flag = 1;
				strcpy(code, xelement);
			}
			else
			{
				int *p = codein, *q = codein;
				while(ncode--)
				{
					j = *q++;
					if(code[j] != xelement[j])	code[j] = '.';
					else *p++ = j;
				}
				if((ncode = p - codein) == 0)	break;
				lastcode = codein[ncode - 1];
			}
#ifdef DEBUG6
			printf("code     : %s\n", code);
#endif
		}

		if(sp[n] == 0)
		{
			i = n1;
			j = m1;
			do
			{
				j -= (runs[i] + 1);
				if(i <= 0)	break;
			} while(sp[i--] == 1);
			do
			{
				if(lastcode <= j)	break;
				if(code[lastcode] != '.')
				{
#ifdef SETCHECK
					if(code[lastcode] == '1')	set1(masks + lastcode);
					else						set0(masks + lastcode);
#else
					masks[lastcode] = code[lastcode];
#endif
					fix[nfix++] = lastcode;
				}
				ncode--;
				lastcode = codein[ncode - 1];
			} while(ncode > 0);
			if(ncode == 0)	break;
		}

#ifdef DEBUG6
		printf("* sp[] increment process *  ");
#endif
		int check;

		if(unmatch == m)
		{
#ifdef DEBUG6
			printf("(matched case)\n");
#endif
			if((i = inccheck(sp, n)) < 0)	break;
			check = lastcode;
		}
		else
		{
#ifdef DEBUG6
			printf("(unmatched case)\n");
#endif
			for(i = 0, j = 0; i < n; i++)
				if((j += (sp[i] + runs[i])) > unmatch)	break;
			if(xelement[unmatch] == '0')	i--;
			check = unmatch;
		}

#ifdef DEBUG6
		printf("change = %d\n", i);
#endif
		k = srun[i] + sp[i];
		for(j = i - 1; j >= 0;)	k += sp[j--];
		while(k > check)
		{
#ifdef DEBUG6
			printf("change point=%d, lastcode=%d\n", k, lastcode);
#endif
			if(--i < 0)	goto ret;
			k -= (sp[i + 1] + runs[i]);
		}
		if(incsp1(sp, totalsp, n, i) == 0)	break;
#ifdef DEBUG6
		matprint(sp, n + 1, "new sp");
#endif
		if(sp0 != sp[0])
		{
			sp0 = sp[0];
			do
			{
				if((k = fix[startfix]) >= sp0)	break;
				if(masks[k] == '1')	goto ret;
			} while(++startfix < nfix);
			if(k == sp0 && masks[k] == '0')
			{
				do
				{
					sp0++;
				} while(masks[sp0] == '0');
				if((sp[n] = rest - sp0) < 0)	break;
				sp[0] = sp0;
				for(int i = 1; i < n; i++)	sp[i] = 1;
			}
		}
#ifdef DEBUG6
		putchar('\n');
#endif
	}
ret:

#ifdef DEBUG13
	printf("* allcheck last process   flag=%d\n", flag);
	printf("mask : %s\ncode : %s\n", masks, code);
#endif
/*	if(flag)	strcpy(masks, code);*/

	if(flag)
	{
#ifdef SETCHECK
		i = 0;
		do
		{
			if     (code[i] == '1')	set1(masks + i);
			else if(code[i] == '0')	set0(masks + i);
		} while(++i < m);
#else
		strcpy(masks, code);
#endif
	}

	remake(mask1, masks, sets, m);

#ifdef DEBUG13
	printf("< allcheck out >\nmask : %s\n", mask1);
	printf("number of loop = %ld\n", count);
#endif
	return;
}

void rest0(int *run, char *mask, int n)
{
	char *p = mask;
	int *q = run;
#ifdef SETCHECK
	if(n == 0)	while(*p)	set0(p++);
#else
	if(n == 0)	while(*p)	*p++ = '0';
#endif
	else
	{
		for(int i = 0; i < n; i++)
		{
#ifdef SETCHECK
			int j = *q++;
			while(j--)	set1(p++);
			if(i == n - 1)	break;
			set0(p++);
#else
			int j = *q++;
			while(j--)	*p++ = '1';
			if(i == n - 1)	break;
			*p++ = '0';
#endif
		}
	}
}

int inccheck(int *sp, int n)
{
	if(sp[n] > 0)	return n - 1;
	if(n == 1)	return -1;
	while(--n)	if(sp[n] != 1)	return n - 1;
	return -1;
}

int incsp1(int *sp, int totalsp, int n, int i)
{
	sp[i]++;
	for(int j = i + 1; j < n;)	sp[j++] = 1;
	for(j = 0; j < n;)	totalsp -= sp[j++];
	if((sp[n] = totalsp) >= 0)	return 1;
	if(--i < 0)	return 0;

	for(;;)
	{
		sp[i]++;
		totalsp += (sp[i + 1] - 2);
		sp[i + 1] = 1;
		if((sp[n] = totalsp) >= 0)	return 1;
		if(--i < 0)	return 0;
	}
}

char *newchar(int n)
{
	char *p = new char[n + 1];
	if(p == NULL)	memover();
	*(p + n) = '\0';
	return p;
}

int *newint(int n)
{
	if(n == 0)	return NULL;
	int *p = new int[n];
	if(p == NULL)	memover();
	return p;
}

int **newpint(int n)
{
	int **p = new pint[n];
	if(p == NULL)	memover();
	return p;
}

char **newpchar(int n)
{
	char **p = new pchar[n];
	if(p == NULL)	memover();
	return p;
}

#ifdef DEBUG2
int runcycle = 0;
#define	po_()	printf("< runcheck out : cycle %d >\nmask : %s\n", runcycle--, mask);
#else
#define	po_()
#endif

#ifdef DEBUG1
#define	ps_(a)	printf("runcheck process - %d  start\nmask : %s\n", a, mask);
#define	pe_(a)	printf("runcheck process - %d  end\nmask : %s\n", a, mask);
#else
#define ps_(a)
#define pe_(a)
#endif

void runcheck(int *run, char *mask, int m, int n)
{
	if(errflag == 0 && errset == 1)	return;
#ifdef DEBUG2
	printf("<runcheck in : cycle %d > m=%d n=%d\n", ++runcycle, m, n);
	printf("mask : %s\n", mask);
	matprint(run, n, "run");
#endif

	int m1 = m - 1, n1 = n - 1;

	if(n < 0 || m <= 0 || checkmask(mask))
	{
		po_();
		return;
	}

	int run0 = run[0];

	if(n == 0 || run0 == 0)
	{
		ps_(1);
		char *p = mask;
		while(m--)	*p++ = '0';
		pe_(1);
		po_();
		return;
	}

	int rest = calrest(run, m, n);

	if(rest == 0)
	{
		ps_(2);
		rest0(run, mask, n);
		pe_(2);
		po_();
		return;
	}

	for(int i = 0; i < n;)	if(run[i++] > rest)	break;
	if(i < n)
	{
		ps_(3);
		i = 0;
		int j, nrun = 0;
		for(;;)
		{
			if((j = run[nrun] - rest) > 0)
			{
				int k = rest;
				while(k--)	i++;
#ifdef SETCHECK
				while(j--)	set1(mask + i++);
#else
				while(j--)	mask[i++] = '1';
#endif
			}
			else
			{
				int k = run[nrun];
				while(k--)	i++;
			}
			if(nrun++ == n1)	break;
			i++;
		}
		pe_(3);
	}

	if(run0 != 1 && mask[run0] == '0' && mask[run0 - 1] == '1')
	{
		ps_(4);
#ifdef SETCHECK
		for(i = run0 - 2; i >= 0;)	set1(mask + i--);
#else
		for(i = run0 - 2; i >= 0;)	mask[i--] = '1';
#endif
		pe_(4);
	}

	int runn1 = run[n1];

	if(runn1 != 1 && mask[m1 - runn1] == '0' && mask[m - runn1] == '1')
	{
		ps_(5);
#ifdef SETCHECK
		for(i = runn1 - 2; i >= 0;)	set1(mask + m1 - i--);
#else
		for(i = runn1 - 2; i >= 0;)	mask[m1 - i--] = '1';
#endif
		pe_(5);
	}

	if(mask[run0] == '1')
	{
		ps_(6);
#ifdef SETCHECK
		set0(mask);
#else
		mask[0] = '0';
#endif
		pe_(6);
	}

	if(mask[m1 - runn1] == '1')
	{
		ps_(7);
#ifdef SETCHECK
		set0(mask + m1);
#else
		mask[m1] = '0';
#endif
		pe_(7);
	}

	if(run0 > 1)
	{
		ps_(8);
		for(i = run0 - 1; i > 0; i--)
		{
			if(mask[i] == '0')
			{
#ifdef SETCHECK
				for(i--; i >= 0;)	set0(mask + i--);
#else
				for(i--; i >= 0;)	mask[i--] = '0';
#endif
				break;
			}
		}
		pe_(8);

		ps_(9);
		for(i = run0 - 1; i > 0; i--)
		{
			if(mask[i] == '1')
			{
#ifdef SETCHECK
				for(i++; i < run0;)	set1(mask + i++);
#else
				for(i++; i < run0;)	mask[i++] = '1';
#endif
				break;
			}
		}
		pe_(9);
	}

	if(runn1 > 1)
	{
		ps_(10);
		for(i = m - runn1; i < m1; i++)
		{
			if(mask[i] == '0')
			{
#ifdef SETCHECK
				for(i++; i < m;)	set0(mask + i++);
#else
				for(i++; i < m;)	mask[i++] = '0';
#endif
				break;
			}
		}
		pe_(10);

		ps_(11);
		for(i = m - runn1; i < m1; i++)
		{
			if(mask[i] == '1')
			{
#ifdef SETCHECK
				for(i--; i >= m - runn1;)	set1(mask + i--);
#else
				for(i--; i >= m - runn1;)	mask[i--] = '1';
#endif
				break;
			}
		}
		pe_(11);
	}

	if(mask[0] == '0')
	{
		ps_(12);
		i = 1;
		m--;
		while(mask[i] == '0')
		{
			i++;
			m--;
		}
		runcheck(run, mask + i, m, n);
		pe_(12);
		po_();
		return;
	}

	if(mask[m1] == '0')
	{
		ps_(13);
		m--;
		while(mask[m - 1] == '0')	m--;
		mask[m] = '\0';
		runcheck(run, mask, m, n);
		mask[m] = '0';
		pe_(13);
		po_();
		return;
	}

	if(mask[0] == '1')
	{
		ps_(14);
#ifdef SETCHECK
		for(i = 1; i < run0;)	set1(mask + i++);
		set0(mask + i);
#else
		for(i = 1; i < run0;)	mask[i++] = '1';
		mask[i] = '0';
#endif
		i++;
		runcheck(run + 1, mask + i, m - i, n1);
		pe_(14);
		po_();
		return;
	}

	if(mask[m1] == '1')
	{
		ps_(15);
#ifdef SETCHECK
		for(i = 1; i < runn1;)	set1(mask + m1 - i++);
		int k = m1 - i++;
		set0(mask + k);
#else
		for(i = 1; i < runn1;)	mask[m1 - i++] = '1';
		k = m1 - i++;
		mask[k] = '0';
#endif
		mask[k] = '\0';
		runcheck(run, mask, m - i, n1);
		mask[k] = '0';
		pe_(15);
		po_();
		return;
	}

	if(mask[1] == '1')
	{
		ps_(16);
#ifdef SETCHECK
		if(mask[run0 + 1] == '1')
		{
			set1(mask);
			set0(mask + run0);
		}
		for(i = 2; i < run0;)	set1(mask + i++);
#else
		if(mask[run0 + 1] == '1')
		{
			mask[0] = '1';
			mask[run0] = '0';
		}
		for(i = 2; i < run0;)	mask[i++] = '1';
#endif
		i++;
		runcheck(run + 1, mask + i, m - i, n1);
		pe_(16);
		po_();
		return;
	}

	if(mask[m - 2] == '1')
	{
		ps_(17);
		if(mask[m1 - runn1 - 1] == '1')
		{
#ifdef SETCHECK
			set1(mask + m1);
			set0(mask + m1 - runn1);
#else
			mask[m1] = '1';
			mask[m1 - runn1] = '0';
#endif
		}
#ifdef SETCHECK
		for(i = 2; i < runn1;)	set1(mask + m1 - i++);
#else
		for(i = 2; i < runn1;)	mask[m1 - i++] = '1';
#endif
		i++;
		m -= i;
		int j = mask[m];
		mask[m] = '\0';
		runcheck(run, mask, m, n1);
		mask[m] = j;
		pe_(17);
		po_();
		return;
	}

	ps_(18);
	char *mask1 = newchar(m + 1);

	for(int nrun = 2; nrun < n; nrun++)
	{
		int maxrun = run0, j = run0 + 1, k;
		for(i = 1; i < nrun; i++)
		{
			if(maxrun < run[i])	maxrun = run[i];
			j += (run[i] + 1);
		}
		char *pattern = newchar(maxrun + 3), *p = pattern;

		*p++ = '.';
		for(i = maxrun; i--;)	*p++ = '1';
		*p++ = '.';
		*p = '\0';
		strcpy(mask1, mask);
		mask1[j] = '\0';
		while((k = leftfind(mask1, pattern)) >= 0)
		{
#ifdef SETCHECK
			set0(mask + k);
			set0(mask + k + maxrun + 1);
#else
			mask[k] = '0';
			mask[k + maxrun + 1] = '0';
#endif
			mask1[k] = mask1[k + maxrun + 1] = '0';
		}
		delete pattern;
	}
	pe_(18);

	ps_(19);
	for(nrun = 2; nrun < n; nrun++)
	{
		int maxrun = runn1, j = runn1 + 1, k;
		for(i = 1; i < nrun; i++)
		{
			if(maxrun < run[n1 - i])	maxrun = run[n1 - i];
			j += (run[n1 - i] + 1);
		}
		char *pattern = newchar(maxrun + 3), *p = pattern;

		*p++ = '.';
		for(i = maxrun; i--;)	*p++ = '1';
		*p++ = '.';
		*p = '\0';
		for(i = 0; i < j; i++)	mask1[i] = mask[m1 - i];
		mask1[j] = '\0';
		while((k = leftfind(mask1, pattern)) >= 0)
		{
#ifdef SETCHECK
			set0(mask + m1 - k);
			set0(mask + m1 - k - maxrun - 1);
#else
			mask[m1 - k] = '0';
			mask[m1 - k - maxrun - 1] = '0';
#endif
			mask1[k] = mask1[k + maxrun + 1] = '0';
		}
		delete pattern;
	}
	delete mask1;
	pe_(19);

	if(strchr(mask, '1') || strchr(mask, '0'))
	{
		int maxrun = run0, minrun = run0;
		for(i = 1; i < n; i++)
		{
			if(run[i] > maxrun)	maxrun = run[i];
			else if(run[i] < minrun)	minrun = run[i];
		}

		if(strchr(mask, '1'))
		{
			ps_(20);
			int j = 0;
			for(i = 0; i < m; i++)
			{
				if(mask[i] != '1')	j = 0;
				else if(++j == maxrun)
				{
					i++;
#ifdef SETCHECK
					if(i < m)	set0(mask + i);
					if((j = i - maxrun - 1) >= 0)	set0(mask + j);
#else
					if(i < m)	mask[i] = '0';
					if((j = i - maxrun - 1) >= 0)	mask[j] = '0';
#endif
					j = 0;
				}
			}
			pe_(20);
		}

		if(strchr(mask, '0'))
		{
			ps_(21);
			if(minrun > 1)
			{
				char *pattern = newchar(minrun + 3), *p;
				for(i = 1; i < minrun; i++)
				{
					p = pattern;
					*p++ = '0';
					for(int j = i; j--;)	*p++ = '.';
					*p++ = '0';
					*p = '\0';
					while((j = leftfind(mask, pattern)) >= 0)
					{
						p = mask + j + 1;
						int k = i;
#ifdef SETCHECK
						while(k--)	set0(p++);
#else
						while(k--)	*p++ = '0';
#endif
					}
				}
				delete pattern;
			}
			pe_(21);
		}
	}

	ps_(22);
	run10(run, mask, m, n);
	pe_(22);

	ps_(23);
	mask1 = newchar(m + 1);
	int j = n1, *run1  = newint(n);

	char *p = mask1 + m1, *q = mask;
	while(*q)	*p-- = *q++;
	mask1[m] = '\0';
	for(i = 0; i < n;)	run1[i++] = run[j--];

	run10(run1, mask1, m, n);

	p = mask1 + m1;
	q = mask;
	do
	{
#ifdef SETCHECK
		if     (*p == '1')	set1(q);
		else if(*p == '0')	set0(q);
#else
		if     (*p == '1')	*q = '1';
		else if(*p == '0')	*q = '0';
#endif
		p--;
	} while(*(++q));
	delete mask1;
	delete run1;
	pe_(23);

	ps_(24);
	for(nrun = 1; nrun < n; nrun++)
	{
		int maxrun = 0, k;
		i = rest;
		for(int j = nrun - 1; j >= 0; j--)
		{
			if(maxrun < run[j])	maxrun = run[j];
			if((i -= (run[j] + 1)) < 0)	break;
		}
		for(i = 0, k = 0; i < nrun; i++)	k += (run[i] + 1);
		i = 0;
		while(mask[k + i] == '1')	i++;
		if(i)
		{
#ifdef SETCHECK
			if(i == maxrun)	set0(mask + k - 1);
#else
			if(i == maxrun)	mask[k - 1] = '0';
#endif
		}
		else
		{
			for(i = 1; i <= run[nrun]; i++)	if(mask[k + i] == '1')	break;
			if(i <= run[nrun])
			{
				j = k + i;
				i = 1;
				while(mask[j + i] == '1')	i++;
				if(maxrun < run[nrun])	maxrun = run[nrun];
				if(i == maxrun)
				{
#ifdef SETCHECK
					set0(mask + j - 1);
					set0(mask + j + i);
#else
					mask[j - 1] = mask[j + i] = '0';
#endif
				}
			}
		}
	}
	pe_(24);

	ps_(25);
	for(nrun = n - 2; nrun >= 0; nrun--)
	{
		int maxrun = 0, k;
		i = rest;
		for(int j = nrun + 1; j < n; j++)
		{
			if(maxrun < run[j])	maxrun = run[j];
			if((i -= (run[j] + 1)) < 0)	break;
		}
		for(i = n1, k = m1; i > nrun; i--)	k -= (run[i] + 1);
		i = 0;
		while(k - i >= 0 && mask[k - i] == '1')	i++;
		if(i)
		{
#ifdef SETCHECK
			if(i == maxrun)	set0(mask + k + 1);
#else
			if(i == maxrun)	mask[k + 1] = '0';
#endif
		}
		else
		{
			for(i = 1; i <= run[nrun]; i++)	if(mask[k - i] == '1')	break;
			if(i <= run[nrun])
			{
				j = k - i;
				i = 1;
				while(mask[j - i] == '1')	i++;
				if(maxrun < run[nrun]) maxrun = run[nrun];
				if(i == maxrun)
				{
#ifdef SETCHECK
					set0(mask + j + 1);
					set0(mask + j - i);
#else
					mask[j + 1] = mask[j - i] = '0';
#endif
				}
			}
		}
	}
	pe_(25);
	po_();
	return;
}

void run10(int *run, char *mask, int m, int n)
{
	int i, j;

#ifdef DEBUG11
	printf("< run10 in >   m=%d, n=%d\nmask : %s\n", m, n, mask);
	matprint(run, n, "run");
#endif

	int k = 0;
	while((i = leftfind(mask + k, "10")) >= 0)
	{
		k += i;
		int nrun = 1;
		for(int ii = k - 1; ii >= 0 && mask[ii] == '1'; ii--)	nrun++;
		k++;
		int flag = 0, minrun = m;
		for(i = 0, j = run[i]; ; i++)
		{
			if(nrun <= run[i] && j <= k)
			{
				flag++;
				if(minrun > run[i])	minrun = run[i];
			}
			if(i == n - 1)	break;
			j += (run[i + 1] + 1);
		}

#ifdef DEBUG11
		printf("k=%d, nrun=%d, minrun=%d, flag=%d\n", k, nrun, minrun, flag);
#endif
#ifdef SETCHECK
		for(i = 0; i < minrun - nrun; i++)	set1(mask + ii--);
		if(flag == 1)	set0(mask + ii);
#else
		for(i = 0; i < minrun - nrun; i++)	mask[ii--] = '1';
		if(flag == 1)	mask[ii] = '0';
#endif
	}

#ifdef DEBUG11
	printf("< run10 out >\nmask : %s\n", mask);
#endif
}

void shrinkmask(int *run, char *mask, int m, int n,
	int *newrun, char *newmask, int *set, int *mm, int *nn)
{
#ifdef DEBUG4
	printf("< shrinkmask in > m=%d,n=%d\nmask : %s\n", m, n, mask);
	matprint(run, n, "run");
#endif

	int i = 0, mm1 = m, nn1 = n, startrun = 0;
	do
	{
		while(mask[i] == '0')
		{
			i++;
			mm1--;
		}
		if(mask[i] == '.')	break;
		do
		{
			mm1--;
		} while(mask[++i] == '1');
		startrun++;
		if(mask[i] == '0')
		{
			i++;
			mm1--;
		}
	} while(--nn1 != 0);

	int startmask = m - mm1;

#ifdef DEBUG4
	printf("startmask=%d, startrun=%d, mm1=%d, nn1=%d\n",
		startmask, startrun, mm1, nn1);
#endif

	if(nn1)
	{
		i = m - 1;
		do
		{
			while(mask[i] == '0')
			{
				i--;
				mm1--;
			}
			if(mask[i] == '.')	break;
			do
			{
				mm1--;
			} while(mask[--i] == '1');
			if(mask[i] == '0')
			{
				i--;
				mm1--;
			}
		} while(--nn1 != 0);
	}

#ifdef DEBUG4
	printf("mm1=%d, nn1=%d\n", mm1, nn1);
#endif

	if(leftfind(mask + startmask, "00") == -1)
	{
#ifdef DEBUG4
		printf("***  Not find '00' code  ***\n");
#endif
		strcpy(newmask, mask + startmask);
		newmask[mm1] = '\0';
		for(i = 0; i < mm1;)	set[i++] = startmask++;
	}
	else
	{
#ifdef DEBUG4
		printf("***  Find '00' code  ***\n");
#endif
		int j = startmask, k = 1, inew = 0, nset = 0;
		m = mm1;
		for(i = 0; i < m; i++)
		{
			if(k || mask[j] != '0')
			{
				newmask[inew++] = mask[j];
//				set[nset++] = j;
				set[nset++] = i + startmask;
			}
			else	mm1--;
//			k = (mask[j++] != '0');
			k = (mask[j++] != '0')? 1: 0;
		}
		newmask[inew] = '\0';
	}
	for(i = 0; i < nn1;)	newrun[i++] = run[startrun++];

#ifdef DEBUG4
	printf("< shrinkmask out > mm=%d,nn=%d\n", mm1, nn1);
	printf("newmask : %s\n", newmask);
	matprint(newrun, nn1, "newrun");
	matprint(set, mm1, "set");
#endif

	*mm = mm1;
	*nn = nn1;
}

void remake(char *mask, char *mask1, int *set, int m)
{
	while(m--)
	{
		char c = mask1[m];
#ifdef SETCHECK
		if	   (c == '1')	set1(mask + set[m]);
		else if(c == '0')	set0(mask + set[m]);
#else
		if	   (c == '1')	mask[set[m]] = '1';
		else if(c == '0')	mask[set[m]] = '0';
#endif
	}
}

int leftfind(char *mask, char *pattern)
{
	int m = strlen(mask);
	int mm = m - strlen(pattern) + 1;
	int i = 0;
	do
	{
		char *p = pattern;
		if(mask[i] != *p)	i++;
		else
		{
			int j = i;
			do
			{
				if(*(++p) == '\0')	return j;
				if(++i == m)	return -1;
			} while(*p == mask[i]);
		}
	} while(i < mm);
	return -1;
}