野人传教士.cpp

野人传教士问题的一种简单实现方法

 #include <stdio.h>
#include <memory.h>
#include <algorithm>
 #include <stack>
 using namespace std;
 
 struct state{
 	int man;
 	int tiger;
 	int boat;
 	
 	state(int m, int t, int b) : man(m), tiger(t), boat(b){};
 };
 
 bool visited[4][4][2];
 int change[10][3] = {{-2, 0, 1},{-1,-1,1}, {0,-2,1}, {2,0,0},{1,1,0}, {0,2,0}, {-1, 0, 1},{1, 0, 0},{0,1,0},{0,-1,0}};
 stack<state> s;
 state begin(3,3,0);
 state end(0, 0, 1);
 
 void init()
 {
 	for (int i = 0; i < 4; i++)
 		for (int j = 0; j < 4; j++)
 			memset(visited[i][j], false, sizeof(bool)*2);
 			
 	s.push(begin);
 }
 
 void dfs()
 {
 	if ( s.size() <= 0 )
 		return;
 	state t = s.top();
 	
 	if ( !visited[t.man][t.tiger][t.boat] )
 	{
 		bool flag = false;
 		
 		for ( int i = 0; i < 10; i++)
 		{
 			int tman = t.man + change[i][0];
 			int ttiger = t.tiger + change[i][1];
 			int tboat = change[i][2];
 			
 			if ( tboat == t.boat )
 				continue;
 				
 			state tstate(tman, ttiger, tboat);
 			
 			if ( visited[tman][ttiger][tboat] )
 				continue;
			
 			if ( (tman < ttiger && tman != 0 ) || (tman > ttiger && tman != 3 ) )
 				continue;
 			else
 			{
 				if ( tstate.man == end.man && tstate.tiger == end.tiger && tstate.boat == end.boat )
 				{
 					s.push(tstate);
 					printf("Solution found! %d steps are required.\n", s.size());
 					printf("The road from terminated State to initial state:\n");
 					
 					while ( s.size() > 0 )
 					{
 						state temp = s.top();
 						printf("(%d, %d, %d) ", temp.man, temp.tiger, temp.boat);
 						if ( s.size() == 1 )
 							printf("\n");
 						else
 							printf(" <--- ");
 						s.pop();		
 					}
 				}
 				s.push(tstate);
 				visited[t.man][t.tiger][t.boat] = true;
 				flag = true;
 				
 				dfs();
 			}
 		}
 		if ( !flag )
			s.pop();
 	}
 	else
 	{
 		s.pop();
 	}
 	
 }
 
 int main()
 {
 	init();
 	dfs();
 	return 0;
 }