/*
 *** boat7.c: 川渡り問題 (7)：　汎用の探索ルーチンの分離 ***
 *	(2004/06/21 YH)
 *
 *** コンパイル方法
 *	% cc -o boat7 boat7.c search.c
 *　　あるいは：
 *	% cc -c search.c		←これは１回だけやればよい。
 *	% cc -o boat7 boat7.c search.o
 */

#include "search.h"
#include <string.h>

#define	NODES	16			// 状態の総数 2^4 = 16
#define	LEFT	0			// 左岸にいる状態
#define	RIGHT	1			// 右岸にいる状態
#define	T	0x01			// T: 第１ビット（最下位ビット）
#define	W	0x02			// W: 第２ビット
#define	G	0x04			// G: 第３ビット
#define	C	0x08			// C: 第４ビット
#define	ALLRIGHT	(T | W | G | C)
#define	ALLLEFT		0

#define	INFINITY	100		// （実質的に）無限大

struct NODE {				// 状態を表す構造体（配列は経路を表す）
	int pos;			// 状態のビットマップ表現
	int inhibit;			// 禁止状態なら 1、そうでなければ 0
	int final;			// 目標状態なら 1、そうでなければ 0
	int len;			// このノードに到達するまでの経路長
	struct NODE *link[4];		// 移動可能なノードへのリンク
	int nl;				// その本数
	char left[5], right[5];		// 左右岸にいるものの文字列表現
} node[NODES];

/*
 */

int
same_side(pos, members)
	int pos; int members;
{
	int filter = pos & members;
	return ((filter == members) || (filter == 0));
}

void
newlink(nd, members)			// 合法な新しいリンクを登録する
	struct NODE *nd; int members;
{
	int move = nd->pos ^ members;
	if (!same_side(nd->pos, members)) return;	// 移動者が同じ岸にいるか？
	if (node[move].inhibit) return;			// 移動先は禁止状態でないか？
	nd->link[nd->nl++] = node + move;
}

void
initialize()				// 状態ノードの初期化
{
	int i, j, k;
	for (i=0; i<NODES; i++) {	// ステップ１：各状態ノードの情報設定
		struct NODE *nd = node + i;
		nd->pos = i;
		nd->inhibit = !same_side(i, T|G) && (same_side(i, W|G) || same_side(i, G|C));
		nd->final = (i == ALLRIGHT);
		nd->len = INFINITY;
		nd->nl = 0;

		strcpy(nd->left,  "TWGC");	// 左岸、右岸の出力文字列の設定
		strcpy(nd->right, "TWGC");
		for (j=0, k=i; j<4; j++, k>>=1) {
			if (k & 1) nd->left[j] = ' ';
			else	   nd->right[j] = ' ';
		}
	}
	for (i=0; i<NODES; i++) {	// ステップ２：移動可能な状態へのリンク設定
		struct NODE *nd = node + i;
		newlink(nd, T);
		newlink(nd, (T|W));
		newlink(nd, (T|G));
		newlink(nd, (T|C));
	}
	node[0].pos = ALLLEFT;
}

void
print_answer(n, len)			// 見つかった解答の出力
	int n, len;
{
	int i, j, move;
	struct NODE **nodes;

	for (i=1; i<=n; i++) {
		printf("*** Answer #%d ***\n", i);
		nodes = (struct NODE **)answer_path(i);
		for (j=0; j<=len; j++) {
			if (j > 0) {
				int move = nodes[j]->pos ^ nodes[j-1]->pos, k;
				printf("               %s", (nodes[j]->pos & 1)? "[": "<=[");
				for (k=0; k<4; k++, move>>=1) if (move & 1) printf("%c", "TWGC"[k]);
				printf("%s\n", (nodes[j]->pos & 1)? "]=>": "]");
			}
			printf("%5d.  [%s] ====== [%s]\n", j, nodes[j]->left, nodes[j]->right);
		}
		printf("\n");
	}
}

int
node_status(nd, len, next)
	struct NODE *nd, **next; int len;
{
	int i, j=0;

	if (nd->final) return(SUCCESS);
	nd->len = len;
	for (i=0; i<nd->nl; i++) if (nd->link[i]->len > len) next[j++] = nd->link[i];
	return(j);
}

void
main(argc, argv)
	int argc; char **argv;
{
	int n;
	printf("\n*** Depth First Search ***\n\n");
        initialize();
        n = depth_first(node);
	print_answer(n, answer_length());

        printf("\n*** Breadth First Search ***\n\n");
        initialize();
        n = breadth_first(node);
	print_answer(n, answer_length());
}