#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct Node{
int x;//左岸传教士数
int y;//左岸野人数目
int c;//船是否在左岸，1是，0否
};
vector<Node> answer;
int Q3[8][2]={{0,3},{3,0},{2,1},{0,2},{2,0},{1,1},{1,0},{0,1}};//船能承载三人时，可能的渡河情况
bool e[1500];//记录某一状态是否探索过，使用散列函数（x+y*20+c*1000）
bool crossBy2(int N);//船能承载两人时
bool crossBy3(int N);//船能承载三人时
佟丽娅怀孕void simpleCross(int k);//船能承载三人以上时
int main(int argc,char*argv[])
{
int N,k;
ifstream fin(argv[1]);
if(!fin){
cout <<"Can't Open File!\n";
return -1;
}
fin >> N >> k;
fin.close();
for(int i=0;i<1500;i++)
e[i]=false;
ofstream fout(argv[2]);
王思聪 花千芳if(k < 2){//一定无解
fout << "no solution" << endl;
return 0;
}
/
/初始状态存入结果向量
Node n;
n.x = N;
n.y = N;
n.c = 1;
answer.push_back(n);
if(k > 3){
simpleCross(k/2);
}
if(k == 2){
if(!crossBy2(N)){
fout << "no solution" << endl;
return 0;
}
}
if(k == 3){
if(!crossBy3(N)){
fout << "no solution" << endl;
return 0;
}
}
for(unsigned i=0;i<answer.size();i++){
fout <<"(" << answer.at(i).x <<","<<answer.at(i).y<<","<<answer.at(i).c<<")"<<endl;
}
return 0;
王心凌 范植伟}
//k>3，每次渡河传教士和野人人数都相等
void simpleCross(int k){
Node n = answer.at(answer.size()-1);
if(n.x > k){
Node n0,n1;
n0.x = n.x - k;
n0.y = n.y - k;
n0.c = 0;
n1.x = n0.x+1;
n1.y = n0.y+1;
n1.c = 1;
answer.push_back(n0);
answer.push_back(n1);
simpleCross(k);
}else{
Node n0;
n0.x = 0;
n0.y = 0;
n0.c = 0;
answer.push_back(n0);
}
}
bool crossBy2(int N){
Node n = answer.at(answer.size()-1);//获取当前左岸情况the path
int i,j;
if((n.x+n.y) > 2){//不能一次过河
for(i=0; i<5; i++){//试探过河，从左岸到右岸
int tx = n.x-Q2[i][0];
int ty = n.y-Q2[i][1];
if((tx<0) || (ty<0))
continue;
//方案可行
if((!e[tx+ty*20])&&((tx == 0)||(tx == N)||(tx == ty))){
Node n0;
n0.x = tx;
n0.y = ty;
n0.c = 0;
answer.push_back(n0);
e[tx+ty*20]=true;
//试探过河，从右岸到左岸
关之琳演过的电影for(j=4;j>=0;j--){
int ttx = tx+Q2[j][0];
int tty = ty+Q2[j][1];
if((ttx<0) || (tty<0))
continue;
//方案可行
if((!e[ttx+tty*20+1000])&&((ttx == 0)||(ttx == N)||(ttx == tty))){
Node n1;
n1.x = ttx;
n1.y = tty;
n1.c = 1;
answer.push_back(n1);
e[ttx+tty*20+1000] = true;
//递归探索
if(crossBy2(N))
return true;
else{
answer.pop_back();
}
}
}
//当前情况下，从右岸向左岸过河失败
answer.pop_back();
}
}
return false;//从左
岸向右岸过河失败，退回上一层
}else{//渡河成功
Node n0;
n0.x = 0;
n0.y = 0;
n0.c = 0;
answer.push_back(n0);
return true;
}
}
bool crossBy3(int N){
Node n = answer.at(answer.size()-1);//获取当前左岸情况
int i,j;
if((n.x+n.y) > 3){
for(i=0; i<8; i++){//试探过河，从左岸到右岸
int tx = n.x-Q3[i][0];
int ty = n.y-Q3[i][1];
if((tx<0) || (ty<0))
continue;
//方案可行
if((!e[tx+ty*20])&&((tx == 0)||(tx == N)||(tx == ty))){
Node n0;
n0.x = tx;
n0.y = ty;
n0.c = 0;
answer.push_back(n0);
e[tx+ty*20]=true;
for(j=7;j>=0;j--){//试探过河，从右岸到左岸
int ttx = tx+Q3[j][0];
int tty = ty+Q3[j][1];
if((ttx<0) || (tty<0))
continue;
//方案可行
if((!e[ttx+tty*20+1000])&&((ttx == 0)||(ttx == N)||(ttx == tty))){
Node n1;
n1.x = ttx;
n1.y = tty;
n1.c = 1;
answer.push_back(n1);
e[ttx+tty*20+1000] = true;
/
/递归探索
if(crossBy3(N))
return true;
else{
answer.pop_back();
}
}
算你狠 陈小春}
//当前情况下，从右岸向左岸过河失败
answer.pop_back();
}
}
return false;//从左岸向右岸过河失败，退回上一层
}else{//渡河成功
Node n0;
n0.x = 0;
n0.y = 0;
n0.c = 0;
answer.push_back(n0);
return true;
}
}
发布评论