/*
 *** boat1.c: 川渡り問題 (1)：簡単な深さ優先探索 ***
 *	(2004/05/02 YH)
 *
 *** コンパイル方法
 *	% cc -o boat1 boat1.c
 *
 *** 実行方法
 *	% boat1
 *
 *** プログラムの詳細については「プログラムの説明」ページ参照
 *	T: 旅人、W: 狼、G: ヤギ、C: キャベツ
 */

#include <stdio.h>
#include <string.h>

#define	NODES	16			// 状態の総数 2^4 = 16
#define	LEFT	0			// 左岸にいる状態
#define	RIGHT	1			// 右岸にいる状態

struct NODE {				// 状態を表す構造体（配列は経路を表す）
	int T, W, G, C;			// T, W, G, C はそれぞれ LEFT, RIGHT のいずれか
} node[NODES];

int answers = 0;			// 解の個数

int
inhibit(step)				// 禁止状態のチェック：
	int step;			// 　W, C のいずれかと G が T と同じ側にいない
{
	return (
		(node[step].T != node[step].G) &&
		((node[step].T != node[step].W) || (node[step].T != node[step].C))
	);
}

int
previous(step)				// すでに訪れた状態かのチェック
	int step;
{
	int T, W, G, C, i;
	T = node[step].T; W = node[step].W;
	G = node[step].G; C = node[step].C;

	for (i=0; i<step; i++)
		if (	(T == node[i].T) &&
			(W == node[i].W) &&
			(G == node[i].G) &&
			(C == node[i].C) ) return(1);
	return(0);
}

int
final_state(step)			// 目標状態かのチェック
	int step;
{
	return ((node[step].T == RIGHT) &&
		(node[step].W == RIGHT) &&
		(node[step].G == RIGHT) &&
		(node[step].C == RIGHT));
}

void
print_member(step, lr)			// 片岸にいるメンバーの出力
	int step, lr;			// lr は LEFT, RIGHT のいずれか
{
	printf("[");
	if (node[step].T == lr) printf("T"); else printf(" ");
	if (node[step].W == lr) printf("W"); else printf(" ");
	if (node[step].G == lr) printf("G"); else printf(" ");
	if (node[step].C == lr) printf("C"); else printf(" ");
	printf("]");
}

void
print_state(step)			// 見つかった解答の出力
	int step;
{
	int i;

	for (i=0; i<step; i++) printf(":  ");
	printf("%d>> ", step);

	print_member(step, LEFT);
	printf(" === ");
	print_member(step, RIGHT);
	if (final_state(step))	printf(":  %s", "目標状態：　成功");
	if (inhibit(step))	printf(":  %s", "禁止状態：　失敗");
	if (previous(step))	printf(":  %s", "既訪状態：　失敗");
	printf("\n");
}

void
search(step)				// 探索の再帰手続き（深さ優先探索）
	int step;
{
	int next = step + 1;
	int T = node[step].T;

	print_state(step);

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

	node[next].T = 1 - T;			// T は必ず移動する
	node[next].W = node[step].W;
	node[next].G = node[step].G;
	node[next].C = node[step].C;
	search(next);				// T 以外は移動しない場合

	if (node[step].W == T) {		// T と W が移動する場合
		node[next].W = 1-T;
		search(next);
		node[next].W = T;		// 次の呼び出しのため元に戻すのを忘れずに
	}
	if (node[step].G == T) {		// T と G が移動する場合
		node[next].G = 1-T;
		search(next);
		node[next].G = T;
	}
	if (node[step].C == T) {		// T と C が移動する場合
		node[next].C = 1-T;
		search(next);
		node[next].C = T;		// 次がないので、これは戻さなくてもよい
	}
}

void
main(argc, argv)
	int argc; char **argv;
{
	/* 初期状態では T, W, G, C すべてが左岸にいる */
	node[0].T = node[0].W = node[0].G = node[0].C = LEFT;

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