/*
 *** boat6.c: 川渡り問題 (6)：　非再帰的な縦型探索・横型探索の実現 ***
 *	(2004/05/10 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;
	int len;
} pathbuf[MAXPATH], *stack[MAXPATH];
int np = 0, head = 0, tail = 0;

int answers = 0;			// 解の個数

/*
 */

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 push();

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));
	}
	answers = 0;
	head = tail = 0;
	node[0].pos = ALLLEFT;
	push(node, NULL);
}

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

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

void
print_answer(path)			// 見つかった解答の出力
	struct PATH *path;
{
	int i;
	printf("*** Answer #%d ***\n", ++answers);
	print_step(path);			// 移動手順の出力
	printf("\n");
}

void
push(nd, prev)				// 新しい経路ノードの設定
	struct NODE *nd; struct PATH *prev;
{
	struct PATH *path;
	if (np >= MAXPATH) {		// ノード数が多すぎると異常終了
		fprintf(stderr, "path nodes exhausted\n");
		exit(1);
	}
	path = pathbuf + np++;
	path->prev = prev;
	path->node = nd;
	stack[tail++] = path;
	path->len = (prev == NULL)? 0: (prev->len + 1);
	nd->len = path->len;
}

void
expand_nodes(path)
	struct PATH *path;
{
	struct NODE *nd = path->node;
	int i;
	for (i=0; i<nd->nl; i++) if (nd->link[i]->len > nd->len) push(nd->link[i], path);
}

struct PATH *
pop()
{
	return((head == tail)? NULL: stack[--tail]);
}

struct PATH *
dequeue()
{
	return((head == tail)? NULL: stack[head++]);
}

void
depth_first()				// 深さ優先探索
{
	while (head < tail) {
		struct PATH *path = pop();
		if (path->node->final) {	// 目標状態なら結果を出力して探索を続ける。
			print_answer(path);
		} else {
			expand_nodes(path);
		}
	}
}

void
breadth_first()				// 広さ優先探索
{
	while (head < tail) {
		struct PATH *path = dequeue();
		if (path->node->final) {	// 目標状態なら結果を出力して探索を続ける。
			print_answer(path);
		} else {
			expand_nodes(path);
		}
	}
}

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

        printf("\n*** Breadth First Search ***\n\n");
        initialize();
        breadth_first();
}