/*
 *** crock0.c: マスの問題：すべての探索経路を求める ***
 *	usage: crock0 [-ts] A B
 */

#include <stdio.h>

#define	MAXN	50
#define	INFINITY	((A+1)*(B+1)+1)

int A, B, maxd=0;
int dist[MAXN+1][MAXN+1], reached[MAXN*2+1];

void
pour(a,b,d)
	int a,b,d;
{
	if ((a<0) || (a>A) || (b<0) || (b>B)) return;
	if (reached[a] < 0) reached[a] = d;
	if (reached[b] < 0) reached[b] = d;
	if ((reached[a+b] < 0) && (a+b>A) && (a+b>B)) reached[a+b] = d;
	if (dist[a][b] > d) dist[a][b] = d;
}

void
expand(d)
	int d;
{
	int i=0, a,b,d1=d+1;
	for (a=0; a<=A; a++) for (b=0; b<=B; b++) {
		if (dist[a][b] != d) continue;
		i++;
		pour(A, b, d1);
		pour(a, B, d1);
		pour(0, b, d1);
		pour(a, 0, d1);
		pour(0, a+b, d1);
		pour(a+b, 0, d1);
		pour(A, a+b-A, d1);
		pour(a+b-B, B, d1);
	}
	if (i>0) {
		maxd = d;
		expand(d1);
	}
}

void
print_step()
{
	int i, a, b, d;
	for (d=0; d<=maxd; d++) {
		printf("%2d: ", d);
		for (i=0; i<=A+B; i++) {
			printf("%c", ((reached[i]>=0) && (reached[i] <= d))? 'o': 'x');
			if (i % 5 == 0) printf(" ");
		}
		printf(" |");
		for (a=0; a<=A; a++) for (b=0; b<=B; b++) {
			if (dist[a][b] != d) continue;
			printf(" [%2d %2d]", a, b);
		}
		printf("\n");
	}
}

void
print_state()
{
	int a, b;
	printf("\n  A B|");
	for (b=0; b<=B; b++) printf("%3d", b);
	printf("|\n");
	printf("-----+");
	for (b=0; b<=B; b++) printf("---");
	printf("+\n");
	for (a=0; a<=A; a++) {
		printf("%3d  |", a);
		for (b=0; b<=B; b++) if (dist[a][b] == INFINITY) {
			printf(" --");
		} else {
			printf("%3d", dist[a][b]);
		}
		printf("|\n");
	}
	printf("-----+");
	for (b=0; b<=B; b++) printf("---", b);
	printf("+\n");
}

void
abend(cmd)
	char *cmd;
{
	fprintf(stderr, "usage: %s A B (A, B <= %d)\n", cmd, MAXN);
	exit(0);
}

main(argc, argv)
	int argc; char **argv;
{
	int a,b, i,j, n=0, ab[2];
	int opflag = 0, stepflag = 0, stateflag = 0;

	for (i=1; i<argc; i++) {
		if (argv[i][0] == '-') {
			opflag = 1;
			for (j=1; argv[i][j]; j++) switch(argv[i][j]) {
				case 's': stepflag = 1; break;
				case 't': stateflag = 1; break;
			}
		} else {
			if (n >= 2) abend(argv[0]);
			ab[n] = atoi(argv[i]);
			if ((ab[n] < 1) || (ab[n] > MAXN)) abend(argv[0]);
			n++;
		}
	}
	if (n != 2) abend(argv[0]);
	if (opflag == 0) stepflag = stateflag = 1;
	A = ab[0]; B = ab[1];
	
	for (a=0; a<=A+B; a++) reached[a] = -1;
	for (a=0; a<=A; a++) for (b=0; b<=B; b++) dist[a][b] = INFINITY;
	dist[0][0] = 0;
	reached[0] = 0;
	expand(0);

	printf("*** water crock: A=%d, B=%d ***\n", A, B);
	if (stepflag) print_step();
	if (stateflag) print_state();
}