#include "stdafx.h"
#define LEFT  0
#define RIGHT 1
typedef struct{
	int mis, nat;
} Number;
typedef struct{
	Number right, left;
}State;
typedef struct{
	int dir, mis, nat;
}Move;

static State state,ss;

static State History[30];
static Move move[30];
Number boat[]={{1,0},{0,1},{1,1},{2,0},{0,2}};

State move_left(State s, int m, int n){
	State ss;
	ss.left.mis  = s.left.mis  + m;
	ss.left.nat  = s.left.nat  + n;
	ss.right.mis = s.right.mis - m;
	ss.right.nat = s.right.nat - n;
	return ss;
}
State move_right(State s, int m, int n){
	return move_left(s, -m, -n);
}
int safe(State s){
	if(s.left.mis <0 || s.left.nat<0||
	   s.right.mis<0 || s.right.nat<0)return 0;
	if(s.left.mis>=s.left.nat &&
	   s.right.mis>=s.right.nat) return 1;
	if(s.left.mis==0 || s.right.mis==0) return 1;
	return 0;
}
void setHistory(int ip, int dir, int m, int n, State ss){
	History[ip]=ss;move[ip].dir=dir; move[ip].mis=m;move[ip].nat=n;
}
int search(int N, State s, int ip){
	State sn;int m,n,r;
	if(N==0) return 0;
	for(int i=0;i<5;i++){
		m=boat[i].mis, n=boat[i].nat;
		if(m!=move[ip-1].mis || n!=move[ip-1].nat){
			if(safe(ss=move_left(s, m, n))) {
				setHistory(ip,LEFT, m,n,ss);
				if(ss.right.mis==0 && ss.right.nat==0) return ip;
				for(int j=0;j<5;j++){
					if(i!=j){
						sn= move_right(ss, m=boat[j].mis,n=boat[j].nat);
						if(safe(sn)) {
							setHistory(ip+1,RIGHT, m, n, sn);
							if(r=search(N-1, sn,ip+2)) return r;
						}

					}
				}
			}

		}
	}
	return 0;
}
int search(){
	State state={{3,3},{0,0}};int r;
	for(int i=3;i<30;i++){
		setHistory(0, 0, 0, 0, state);
		if(r=search(i,state, 1))return r;
	}
}
void printResult(int N){
	char str[][8]={"left ", "right"};
	printf("\n ---------------------------------------------------------------");
	printf("\n  left bank          right bank"
	       "\n  missionary nature  missionary nature   dir   missionary nature");
	printf("\n ---------------------------------------------------------------");
	printf("\n    %3d       %3d      %3d       %3d",
			History[0].left.mis, History[0].left.nat,
			History[0].right.mis, History[0].right.nat);
	for(int j=1; j<=N;j++){
		printf(" %8s    %3d       %3d",
			str[move[j].dir], move[j].mis, move[j].nat);
		printf("\n    %3d       %3d      %3d       %3d",
			History[j].left.mis, History[j].left.nat,
			History[j].right.mis, History[j].right.nat);
		}
	printf("\n ---------------------------------------------------------------");
}

int _tmain(int argc, _TCHAR* argv[])
{
	int r; if(r=search()) printResult(r);
	getchar();
	return 0;
}