360 필기시험 문제 2013: 목사 (전도사) 와 야인 의 강 건 너 기 문제

360 필기시험 문제 2013: 목사 (전도사) 와 야인 의 강 건 너 기 문제
링크 를 열 려 면 누 르 십시오.처음에 오리지널 을 쓴 것 은 녹색 제목 이 전 재 된 회색 제목 보다 눈 에 띄 기 때 문 이 라 고 생각 하기 때 문 입 니 다. 원작 자 에 게 무례 를 범 했다 면 사과 하 겠 습 니 다.
프로 그래 밍 문제, 선교사 수 M, 야인 C, M ≥ C 는 처음에 모두 해안 왼쪽 에 있 었 다. ① 배 는 두 사람 만 태 울 수 있 고 선교사 와 야인 은 모두 배 를 저 을 수 있다. 물론 누군가가 배 를 저어 야 한다 ② 양안 에서 야인 수 는 선교사 수 보다 많 으 면 안 된다.   모든 사람 을 강 으로 보 내 고 방안 을 설계 하여 프로 그래 밍 실현 을 요구 하 다. 
예전 의 경험 에 따 르 면 예 를 들 어 계단 을 걷 는 문제 (한 번 에 한 걸음 또는 두 걸음 걸 을 수 있 음), 깊이 있 게 검색 하 는 사고 와 한 노 타의 사고, 나 는 이 문제 가 대체적으로 이런 것 이 라 고 생각한다.
A. 현재 상태의 모든 가능성 을 첫 번 째 로 검색 합 니 다.(이것 은 상태 전 이 를 일 으 킬 수 있다)
B. 두 번 째 단 계 는 남 은 하위 문제 에 대해 이 함 수 를 다시 호출 하 는 것 이다. 이것 은 실질 적 으로 깊이 있 게 검색 하 는 사상 이다.
/ * 인용 전재 문장 원 어 부분: * /
상태: 좌 안과 우 안의 인원 + 배의 위치.모든 상태 에서 5 가지 상태 로 이동 할 수 있 습 니 다. 즉, 1. 선교사 2 명 을 대안 으로 운송 합 니 다.2. 야인 2 명 을 맞은편 기슭 으로 운송 하기;3. 선교사 1 명 을 대안 으로 운송 하기;4. 야인 1 명 을 맞은편 기슭 으로 운송 하기;5. 선교사 1 명 과 야인 1 명 을 대안 으로 운송 합 니 다.
초기 상태 부터 이 다섯 가지 상황 을 수색 하고 다음 상태 로 들 어가 이 상태 가 조건 을 충족 시 키 는 지, 즉 양안 야인 의 개수 가 이 해안의 선교사 보다 많은 지, 조건 을 충족 시 키 면 이 상태의 다섯 가지 상황 을 계속 수색 한다.마지막 해 를 찾 을 때 까지 깊이 검색 하 세 요.
주의: 1. 만약 에 검색 상태 가 이전에 이미 나 타 났 다 면 깊이 들 어가 지 않 을 것 입 니 다. 그렇지 않 으 면 죽은 순환 이 나타 날 것 입 니 다. 예 를 들 어 두 명의 야인 을 운반 해서 다시 운반 하고 상태 가 회복 되 었 습 니 다. 계속 이렇게 검색 하면 놀 지 않 을 것 입 니 다.2. 상 태 는 배의 정 보 를 포함 하고 양쪽 의 인원 이 같 지만 배의 위치 가 다르다 면 두 가지 상태 입 니 다.3. 수색 할 목표 상 태 는 사람 이 모두 맞은편 에 있 고 배가 맞은편 에 있다 는 것 이다.
PS: M = C > 3 시 에는 풀 리 지 않 습 니 다.M > C 시 해 가 있 습 니 다.
코드:

#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>
using namespace std;

bool b_OtherSide = true; //true:     
vector<string> visit; //          
struct Option
{
	int W;
	int C;
	Option(int w,int c):W(w),C(c){}
};

Option Op[5]={Option(0,2),Option(2,0),Option(1,1),Option(1,0),Option(0,1)};//      。

bool MoveToOtherSide( int M, int C, int m, int c){
	if( M<0||C<0||m<0||c<0)   //  
		return false;
	if( (M&&C>M) ||(m&&c>m))   //      
		return false;
	
	if( b_OtherSide&&M==0&&C==0 ||(!b_OtherSide&&m==0&&c==0))  //          ，        ，       left->right,      。
		return true;

	//          
	char s[30];
	if( !b_OtherSide )
		sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c);
	else
		sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=right", m,c,M,C);
	string str(s);
	for( int i=0; i<visit.size(); i++)
		if( visit[i]==str)                     //         
			return false;

	visit.push_back(str);
	b_OtherSide = !b_OtherSide;
	for(int i=0;i<5;++i)
	{
		if(MoveToOtherSide(m+Op[i].C,c+Op[i].W,M-Op[i].C,C-Op[i].W))
		{
			printf("%d %d
",Op[i].C,Op[i].W);
			printf("%s
",s);
			return true;
		}
	}
	b_OtherSide = !b_OtherSide;
	visit.pop_back();
	return false;
}

int main(){
	char s[30];
	int M=2,C=2,m=0,c=0;
	sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c);
	printf("%s
",s);
	if(!MoveToOtherSide(M,C,0,0))
		cout << "Can not find the solution."<<endl;
	return 0;
}