/*
 *** crock1.c: 「マスの問題」（探索エンジン使用：広さ優先探索） ***
 */

#include "search.c"

#define	MAXC		50			// マスの容量の最大値
#define	INFINITY	(MAXC+1)*(MAXC+1)+1)	// 事実上の∞

int A, B;					// マス A, B の容量
int v;						// 量りとる値

struct CROCK {			// 状態ノード：水量を index とする２次元配列
	int a, b;				// マス A, B に入っている水量
	int len;				// ここまでの最短経路長
} crock[MAXC+1][MAXC+1];

void
init()						// 初期設定
{
	int a, b;
	for (a=0; a<=A; a++) for (b=0; b<=B; b++) {
		crock[a][b].a = a;		// 値は crock の添字と同じ：
		crock[a][b].b = b;		// 参照用に設定するだけ。
		crock[a][b].len = (A+1)*(B+1)+1;// 初期値は可能な最大値＋１
	}
	crock[0][0].len = 0;			// 初期ノード
}

#define	min(x,y)	(((x)<(y))? (x):(y))	// x, y の小さい方の値

int
node_status(node, len, next_nodes)
	struct CROCK *node, **next_nodes; int len;
{
	int a = node->a, b = node->b, c;
	int n=0;

	if ((a == v) || (b == v)) return(SUCCESS);	// 目標値に到達
	if (node->len < len) return(FAILURE);		// すでに訪問済み
	node->len = len;

		// 以下の処理にはムダがある。例えば最初の行は A を一杯にしているが、
		// すでに一杯であれば何もしていないに等しい。
		// このノードは探索されるときに「訪問済み」として無視されるので
		// 処理には影響ないが、ムダが気になるなら：
		//	if (a < A) next_nodes[n++] = &crock[A][b];
		// などとすればよい。
	next_nodes[n++] = &crock[A][b];		// 蛇口→A（A を一杯にする）
	next_nodes[n++] = &crock[0][b];		// A→流し（A を空にする）
	next_nodes[n++] = &crock[a][B];		// 蛇口→B（B を一杯にする）
	next_nodes[n++] = &crock[a][0];		// B→流し（B を空にする）
	c = min(B, a+b);
	next_nodes[n++] = &crock[a+b-c][c];	// A→B（B が一杯か、A が空になる）
	c = min(A, a+b);
	next_nodes[n++] = &crock[c][a+b-c];	// B→A（A が一杯か、B が空になる）
		// 上で例えば A→B と写すと、[a b] だった水量が
		// [0 a+b], [a+b-B B] の２通りのいずれかになるが、
		// c を使うことでどちらの場合も扱えていることに注意。
	return(n);
}

void
print_answer(n, len, nodes)			// 解経路の出力
	int n, len; struct CROCK **nodes;	// n: 解番号、len: 解の長さ、
{						// nodes: 解ノード列
	int i=0, pa, pb, a=0, b=0;
	char *msg;

	printf("*** %s #%d ***\n", "解", n);
	printf("  -----%2d %2d---------------\n", A, B);
	printf("%4d: [%2d %2d]\t%s\n", 0, nodes[0]->a, nodes[0]->b, "（初期状態）");
	for (i=1; i<=len; i++) { // 前のノードからの水量変化で、移動パターンを割り出す。
		pa = a; pb = b;
		a = nodes[i]->a; b = nodes[i]->b;
		if (a == pa) {			// A に変化なし
			msg = (b == 0)? "B→流し": "蛇口→B";
		} else if (b == pb) {		// B に変化なし
			msg = (a == 0)? "A→流し": "蛇口→A";
		} else {
			msg = (a<pa)? "A→B": "B→A";
		}
		printf("%4d: [%2d %2d]\t%s\n", i, a, b, msg);
	}
	printf("\n");
}

void
main(argc, argv)
	int argc; char **argv;
{
	int i, n, len;
	struct CROCK **ans;
	if (argc != 4) {
		fprintf(stderr, "usage: %s v A B\n", argv[0]);
		fprintf(stderr, "\tv   : %s\n", "量りとる水量");
		fprintf(stderr, "\tA, B: %s\n", "マス A, B の容量");
		exit(1);
	}
	v = atoi(argv[1]);
	A = atoi(argv[2]);
	B = atoi(argv[3]);
	if ((A < 1) || (A > MAXC) || (B < 1) || (B > MAXC)) {
		fprintf(stderr, "A=%d, B=%d: %s%d%s\n", "マスの容量は 1 以上 ", MAXC, " 以下");
		exit(2);
	}
	if ((v < 0) || ((v > A) && (v > B))) {
		fprintf(stderr, "v=%d: %s\n", v, "量りとる水量はマスの容量以下");
		exit(3);
	}

	init();
	n = breadth_first(&crock[0][0]);		// 横型探索
	if (n == 0) {
		printf("\n*** %s ***\n", "解は存在しない");
		exit(0);
	}

	// 解の出力
	printf("\n***** %s=%d, A=%d, B=%d: %s%d %s *****\n\n",
		"量る量", v, A, B, "解：", n, "個");
	len = answer_length();
	for (i=1; i<=n; i++) print_answer(i, len, (struct CROCK **)answer_path(i));
}