/*
ガリ勉小僧とヤンキー兄ちゃんが何人かいます。
ガリ勉小僧とヤンキー兄ちゃんは川の向こうに渡らなければなりません。
舟は一つのみで、一度に乗れる人数は２人までです。
ガリ勉小僧の人数よりヤンキー兄ちゃんの人数が多い場合、
ガリ勉小僧は襲われてメガネを外されてしまいます。
ガリ勉小僧が襲われずに渡るにはどうやって渡ればいいでしょう？
*/

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

int end=0;/* 終了条件 */
char stack[1000][20],wstack[1000][20];/* スタック */
int sp=0,wsp=0;/* スタックポインタ */

/* 以前と同じルートかチェック */
int Check(char *str)
{
	int i;
	for(i=0;i<sp;i++){
		if(strcmp(stack[i],str) == 0){
			return 1;
		}
	}
	return 0;
}

void action(int sen1,int hito1,int sen2,int hito2,int ship)
{
	char str[20];
	if(sen1 < 0 || hito1 < 0 || (sen1 >= 1 && sen1 < hito1))return;
	if(sen2 < 0 || hito2 < 0 || (sen2 >= 1 && sen2 < hito2))return;
	if(sen1==0 && hito1==0 && ship){end = 1;}

	sprintf(str,"(%d,%d,%d,%d,%d)",sen1,hito1,sen2,hito2,ship);

	if(Check(str)){return;}/* 以前と同じルートの場合 */
	strcpy(stack[sp++],str);/* プッシュ */

	if(ship){
		ship = !ship;
		if(!end)action(sen1,hito1+1,sen2,hito2-1,ship);
		if(!end)action(sen1+1,hito1,sen2-1,hito2,ship);
		if(!end)action(sen1+2,hito1,sen2-2,hito2,ship);
		if(!end)action(sen1+1,hito1+1,sen2-1,hito2-1,ship);
		if(!end)action(sen1,hito1+2,sen2,hito2-2,ship);
	}else{
		ship = !ship;
		if(!end)action(sen1,hito1-2,sen2,hito2+2,ship);
		if(!end)action(sen1-1,hito1-1,sen2+1,hito2+1,ship);
		if(!end)action(sen1-2,hito1,sen2+2,hito2,ship);
		if(!end)action(sen1-1,hito1,sen2+1,hito2,ship);
		if(!end)action(sen1,hito1-1,sen2,hito2+1,ship);
	}
	if(end)strcpy(wstack[wsp++],str);
}

int main()
{
	int a,b,i;
	char str[10];
	printf("宣教師の数-->");a = atoi(gets(str));
	printf("人喰い人種の数-->");b = atoi(gets(str));
	action(a,b,0,0,0);
	if(!end){
		puts("このケースじゃダメだな。");
	}else{
		for(i=wsp-1;i>=0;i--){
			printf("%s\n",wstack[i]);
		}
	}
	return 0;
}