/*
 *** boat5.c: 川渡り問題 (5)：　非再帰的な探索 ***
 *	(2004/05/06 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], *stack[NODES];
int 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, 0);
}

void
print_stack(step)			// 探索スタック／キューの出力
	int step;
{
	int i;
	printf("%3d.[%d]: ", step, tail-head);
	for (i=head; i<tail; i++)
		printf(" <%d:[%s]>", stack[i]->len, stack[i]->left);
	printf("\n");
}

void
push(nd, len)				// 新しい経路ノードの設定
	struct NODE *nd; int len;
{
	if (tail >= NODES) {		// ノード数が多すぎると異常終了
		fprintf(stderr, "node stack overflow\n");
		exit(1);
	}
	stack[tail++] = nd;
	nd->len = len;
}

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

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

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

void
depth_first()				// 深さ優先探索
{
	struct NODE *nd;
	int step = 0;
	while (head < tail) {
		print_stack(step++);
		nd = pop();
		if (nd->final) {
			answers++;
		} else {
			expand_nodes(nd);
		}
	}
	print_stack(step);
}

void
breadth_first()				// 広さ優先探索
{
	struct NODE *nd;
	int step = 0;
	while (head < tail) {
		print_stack(step++);
		nd = dequeue();
		if (nd->final) {	// 目標状態なら結果を出力して探索を続ける。
			answers++;
		} else {
			expand_nodes(nd);
		}
	}
	print_stack(step);
}

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