/*
 *** boat3.c: 川渡り問題 (3)：　boat2.c を bitmap 表現に変更 ***
 *	(2004/05/02 YH; revised 04/05/05)
 *
 *** コンパイル方法、実行方法その他は boat1.c, boat2.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

struct NODE {				// 状態を表す構造体（配列は経路を表す）
	int pos;			// 今の場合、構造体にする必要はないが、
} node[NODES];				// 他のプログラムにあわせてある。

int answers = 0;			// 解の個数

int
same_side(nd, members)
	struct NODE *nd; int members;
{
	int filter = nd->pos & members;
	return ((filter == members) || (filter == 0));
}

int
inhibit(nd)				// 禁止状態のチェック
	struct NODE *nd;		// 　W, C のいずれかと G が T と同じ側にいない
{
	return (!same_side(nd, T | G) && (same_side(nd, W | G) || same_side(nd, G | C)));
}

int
previous(nd)				// すでに訪れた状態かのチェック
	struct NODE *nd;
{
	struct NODE *prev;
	int pos = nd->pos;
	for (prev = node; prev != nd; prev++) if (prev->pos == pos) return(1);
	return(0);
}

int
final_state(nd)				// 目標状態かのチェック
	struct NODE *nd;
{
	return (nd->pos == ALLRIGHT);
}

void
print_member(nd, lr)			// 片岸にいるメンバーの出力
	struct NODE *nd; int lr;	// lr は LEFT, RIGHT のいずれか
{
	int pos = nd->pos;
	printf("[");
	printf("%c", "T "[(pos & 1) ^ lr]); pos >>= 1;
	printf("%c", "W "[(pos & 1) ^ lr]); pos >>= 1;
	printf("%c", "G "[(pos & 1) ^ lr]); pos >>= 1;
	printf("%c", "C "[(pos & 1) ^ lr]);
	printf("]");
}

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

	printf("*** Answer #%d ***\n", ++answers);

	for (nd = node; nd<=final; nd++) {
		printf("%5d.  ", nd-node);
		print_member(nd, LEFT);

		if (nd == final)		printf("  ====  ");
		else if ((nd->pos & T) == LEFT)	printf("  ===>  ");
		else				printf("  <===  ");

		print_member(nd, RIGHT);
		printf("\n");
	}
	printf("\n");
}

void
search(nd)				// 探索の再帰手続き（深さ優先探索）
	struct NODE *nd;
{
	struct NODE *next = nd + 1;
	int pos = nd->pos;

	if (final_state(nd)) {		// 目標状態なら結果を出力して探索を続ける。
		print_answer(nd);
		return;
	}
	if (inhibit(nd) || previous(nd)) return;
			// 禁止状態、すでに訪れた状態なら戻る（別経路の探索を続ける）

	next->pos = pos ^ T;			// T 以外は移動しない場合
	search(next);

	if (same_side(nd, T | W)) {		// T と W が移動する場合
		next->pos = pos ^ (T | W);
		search(next);
	}
	if (same_side(nd, T | G)) {		// T と G が移動する場合
		next->pos = pos ^ (T | G);
		search(next);
	}
	if (same_side(nd, T | C)) {		// T と C が移動する場合
		next->pos = pos ^ (T | C);
		search(next);
	}
}

void
main(argc, argv)
	int argc; char **argv;
{
	/* 初期状態では T, W, G, C すべてが左岸にいる */
	node->pos = ALLLEFT;

	search(node);				// 探索手続きの起動
}