/*
 *** boat4.c: 川渡り問題 (4)：　ノードを事前生成、経路リンク使用 ***
 *	(2004/05/02 YH)
 *
 *** コンパイル方法、実行方法その他は、他の boat*.c と同じ
 */

#include <stdio.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];

#define	MAXPATH	100

struct PATH {				// 経路を表す構造体
	struct PATH *prev;		// １つ前の経路ノードへのポインタ
	struct NODE *node;		// この経路ノードが指す状態ノード
} path[MAXPATH];
int np = 0;				// 使用した経路ノードの個数

int answers = 0;			// 解の個数

/*
 */

struct PATH *
newpath(nd, prev)			// 新しい経路ノードの設定
	struct NODE *nd; struct PATH *prev;
{
	struct PATH *p;
	if (np >= MAXPATH) {		// ノード数が多すぎると異常終了
		fprintf(stderr, "too many path nodes\n");
		exit(1);
	}
	p = path + np++;
	p->node = nd;
	p->prev = prev;
	return(p);
}

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));
	}
}

void
print_step(path)			// 移動手順の出力
	struct PATH *path;		// （逆順での出力になるため、再帰呼び出しを使う）
{
	struct NODE *nd;
	if (path == NULL) return;
	print_step(path->prev);		// 先に、これより前の手順を出力しておく

	nd = path->node;
	if (path->prev != NULL) {	// 舟での移動の出力
		int move = nd->pos ^ path->prev->node->pos, i;
		printf("               %s", (nd->pos & 1)? "[": "<=[");
		for (i=0; i<4; i++, move>>=1) if (move & 1) printf("%c", "TWGC"[i]);
		printf("%s\n", (nd->pos & 1)? "]=>": "]");
	}
	printf("%5d.  [%s] ====== [%s]\n", nd->len, nd->left, nd->right);
}

void
print_answer(path)			// 見つかった解答の出力
	struct PATH *path;
{
	int i;
	struct NODE *nd;

	printf("*** Answer #%d ***\n", ++answers);
	print_step(path);		// 移動手順の出力
	printf("\n");
}

void
search(path)				// 探索の再帰手続き（深さ優先探索）
	struct PATH *path;
{
	struct NODE *nd = path->node;
	int i;

	if (nd->final) {		// 目標状態なら結果を出力して探索を続ける。
		print_answer(path);
		return;
	}
	/* nd からリンクのある状態（で、最短経路になるもの）を探索する。 */
	for (i=0; i<nd->nl; i++) if (nd->link[i]->len > nd->len) {
		nd->link[i]->len = nd->len + 1;
		search(newpath(nd->link[i], path));
	}
}

void
main(argc, argv)
	int argc; char **argv;
{
	initialize();			// 初期化処理

	node[0].pos = ALLLEFT;		// 初期状態の設定
	node[0].len = 0;
	search(newpath(node, NULL));	// 探索手続きの起動

	printf("*** path nodes used: %d\n\n", np);
}