早知道要写这么长 就用类写了 呵呵
//copyright by abilitytao,Nanjing University of Science and Technology
//thanks to Mr Xu Chungen
//本程序在商人数<=1000,随从数<=1000时测试通过，其余数据不能保证其正确性.
#include<iostream>
#include <windows.h>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include<time.h>
#include<conio.h>
using namespace std;
#define NMAX 1001
struct node
{
int x;
int y;
}line[100000001];
struct node2
{
int data1;
int data2;
int prex1;
int prey1;
int prex2;
int prey2;
};
node2 a[NMAX][NMAX];
int showpath[NMAX][NMAX];
int main ()
{
int N=30;
while(N--)
{
system("cls");
cout<<endl<<endl<<endl<<endl<<endl;
cout<<" ☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆"<<endl;
cout<<" ★ ★"<<endl;
cout<<" ☆ ☆"<<endl;
cout<<" ★ 欢迎来到商人过河模型演示程序 ★"<<endl;
cout<<" ☆ ☆"<<endl;
cout<<" ★ 制 作：罗伟涛（weitao） ★"<<endl;
cout<<" ☆ 指导老师：许春根（南京理工大学应用数学系） ☆"<<endl;
cout<<" ★ ★"<<endl;
cout<<" ☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆"<<endl<<endl<<endl;
Sleep(150);
system("cls");
cout<<endl<<endl<<endl<<endl<<endl;
cout<<" ★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★"<<endl;
cout<<" ☆ ☆"<<endl;
cout<<" ★ ★"<<endl;
cout<<" ☆ 欢迎来到商人过河模型演示程序 ☆"<<endl;
cout<<" ★ ★"<<endl;
cout<<" ☆ 制 作：罗伟涛（weitao） ☆"<<endl;
cout<<" ★ 指导老师：许春根（南京理工大学应用数学系） ★"<<endl;
cout<<" ☆ ☆"<<endl;
cout<<" ★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★"<<endl<<endl<<endl;
Sleep(150);
}
cout<<"问题描述： 三个商人各带一个随从乘船过河，一只小船只能容纳2人，由他们自己划船。三个商人窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？"<<endl;
cout<<"\n\n\n\n 请按任意键进入演示程序..."<<endl;
char any;
getch();
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int n;
int m;
int i,j;
int flagnum1;
int flagnum2;
while(1)
{
memset(showpath,0,sizeof(showpath));
printf("请输入商人数：");
scanf("%d",&n);
printf("请输入随从数：");
scanf("%d",&m);
if(n>1000)
{
printf("本程序仅在1000以内保证其正确性，请重新输入\n");
continue;
}
if(n<m)
{
printf("商人数显然不可能少于随从数，请重新输入\n");
continue;
}
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(i==0||i==n)
{
a[i][j].data1=1;
a[i][j].data2=1;
continue;
}
if(i>=j&&n-i>=m-j)
{
a[i][j].data1=1;
a[i][j].data2=1;
}
}
}
////////////////////////////////////////////////////////////////////以上为初始化////////////////////////////////////////////////////////////////////////////////
int flag;
int front=1;
int rear=1;
line[rear].x=n;
line[rear].y=m;
flag=1;
flagnum1=1;
flagnum2=0;
while(front<=rear)
{
if(line[front].x==0&&line[front].y==0)
break;
if(flag==1)
{
if(a[line[front].x][line[front].y].data1!=1)
{
flagnum1--;
if(flagnum1==0)
flag=2;
front++;
continue;
}
a[line[front].x][line[front].y].data1=0;
flagnum1--;
if(flagnum1==0)
flag=2;
if(line[front].x-1>=0&&a[line[front].x-1][line[front].y].data2==1)
{
rear++;
line[rear].x=line[front].x-1;
line[rear].y=line[front].y;
a[line[rear].x][line[rear].y].prex2=line[front].x;
a[line[rear].x][line[rear].y].prey2=line[front].y;
flagnum2++;
}
if(line[front].y-1>=0&&a[line[front].x][line[front].y-1].data2==1)
{
rear++;
line[rear].x=line[front].x;
line[rear].y=line[front].y-1;
a[line[rear].x][line[rear].y].prex2=line[front].x;
a[line[rear].x][line[rear].y].prey2=line[front].y;
flagnum2++;
}
if(line[front].x-1>=0&&line[front].y-1>=0&&a[line[front].x-1][line[front].y-1].data2==1)
{
rear++;
line[rear].x=line[front].x-1;
line[rear].y=line[front].y-1;
a[line[rear].x][line[rear].y].prex2=line[front].x;
a[line[rear].x][line[rear].y].prey2=line[front].y;
flagnum2++;
}
if(line[front].x-2>=0&&a[line[front].x-2][line[front].y].data2==1)
{
rear++;
line[rear].x=line[front].x-2;
line[rear].y=line[front].y;
a[line[rear].x][line[rear].y].prex2=line[front].x;
a[line[rear].x][line[rear].y].prey2=line[front].y;
flagnum2++;
}
if(line[front].y-2>=0&&a[line[front].x][line[front].y-2].data2==1)
{
rear++;
line[rear].x=line[front].x;
line[rear].y=line[front].y-2;
a[line[rear].x][line[rear].y].prex2=line[front].x;
a[line[rear].x][line[rear].y].prey2=line[front].y;
flagnum2++;
}
front++;
continue;
}
else if(flag==2)
{
if(a[line[front].x][line[front].y].data2!=1)
{
flagnum2--;
if(flagnum2==0)
flag=1;
front++;
continue;
}
if(line[front].x==0&&line[front].y==0)
break;
a[line[front].x][line[front].y].data2=0;
flagnum2--;
if(flagnum2==0)
flag=1;
if(line[front].x+1<=n&&a[line[front].x+1][line[front].y].data1==1)
{
rear++;
line[rear].x=line[front].x+1;
line[rear].y=line[front].y;
a[line[rear].x][line[rear].y].prex1=line[front].x;
a[line[rear].x][line[rear].y].prey1=line[front].y;
flagnum1++;
}
if (line[front].y+1<=m&&a[line[front].x][line[front].y+1].data1==1)
{
rear++;
line[rear].x=line[front].x;
line[rear].y=line[front].y+1;
a[line[rear].x][line[rear].y].prex1=line[front].x;
a[line[rear].x][line[rear].y].prey1=line[front].y;
flagnum1++;
}
if(line[front].x+1<=n&&line[front].y+1<=m&&a[line[front].x+1][line[front].y+1].data1==1)
{
rear++;
line[rear].x=line[front].x+1;
line[rear].y=line[front].y+1;
a[line[rear].x][line[rear].y].prex1=line[front].x;
a[line[rear].x][line[rear].y].prey1=line[front].y;
flagnum1++;
}
if(line[front].x+2<=n&&a[line[front].x+2][line[front].y].data1==1)
{
rear++;
line[rear].x=line[front].x+2;
line[rear].y=line[front].y;
a[line[rear].x][line[rear].y].prex1=line[front].x;
a[line[rear].x][line[rear].y].prey1=line[front].y;
flagnum1++;
}
if(line[front].y+2<=m&&a[line[front].x][line[front].y+2].data1==1)
{
rear++;
line[rear].x=line[front].x;
line[rear].y=line[front].y+2;
a[line[rear].x][line[rear].y].prex1=line[front].x;
a[line[rear].x][line[rear].y].prey1=line[front].y;
flagnum1++;
}
front++;
continue;
}
front++;
}
if(front>rear)
{
cout<<"没有可行的方案"<<endl;
int choice;
printf("如果您要继续测试，请输入1，退出请输入2:");
scanf("%d",&choice);
if(choice==1)
continue;
else
break;
}
/////////////////////////////////////////////////////////////////以上为搜索过程/////////////////////////////////////////////////////////////////////
int choiceforaction;
int tempx=0;
int tempy=0;
int markx=0;
int marky=0;
int flagforreturn=1;
int step=1;
////////////////////////////////////////////////////////以上是演示变量初始化//////////////////////////////////////////////////////////
printf("请问您需要动态演示还是文字演示(1/0)?:");
scanf("%d",&choiceforaction);
if(choiceforaction==1)
{
if(n>37)
{
printf("商人数大于37时会造成显示错误,请用文字模式显示\n");
continue;
}
printf("由于屏幕宽度的原因，商人数和随从数必须<=37,并且在观看过程中请保证屏幕最大化\n");
system("pause");
int i,j;
system("cls");
showpath[n][m]=1;
for(i=m;i>=0;i--)
{
cout<<i<<' ';
for(j=0;j<=n;j++)
{
if(showpath[j][i]==1)
cout<<'*'<<' ';
else
cout<<" ";
}
cout<<endl;
}
for(i=-1;i<=n;i++)
{
if(i==-1)
{
cout<<"* ";
continue;
}
else
cout<<i%10<<' ';
}
cout<<endl;
cout<<"此时坐标为("<<n<<','<<m<<')'<<endl;
Sleep(1000);
while(1)
{
if (flagforreturn==1)
{
if(markx==n&&marky==m)
break;
flagforreturn=2;
tempx=a[markx][marky].prex2;
tempy=a[markx][marky].prey2;
showpath[n-tempx][m-tempy]=1;
system("cls");
for(i=m;i>=0;i--)
{
cout<<i<<' ';
for(j=0;j<=n;j++)
{
if(showpath[j][i]==1)
cout<<'*'<<' ';
else
cout<<" ";
}
cout<<endl;
}
for(i=-1;i<=n;i++)
{
if(i==-1)
{
cout<<"* ";
continue;
}
else
cout<<i%10<<' ';
}
cout<<endl;
cout<<"此时坐标为("<<n-tempx<<','<<m-tempy<<')'<<endl;
Sleep(1000);
markx=tempx;
marky=tempy;
step++;
}
else if(flagforreturn==2)
{
if(markx==n&&marky==m)
break;
flagforreturn=1;
tempx=a[markx][marky].prex1;
tempy=a[markx][marky].prey1;
showpath[n-tempx][m-tempy]=1;
system("cls");
for(i=m;i>=0;i--)
{
cout<<i<<' ';
for(j=0;j<=n;j++)
{
if(showpath[j][i]==1)
cout<<'*'<<' ';
else
cout<<" ";
}
cout<<endl;
}
for(i=-1;i<=n;i++)
{
if(i==-1)
{
cout<<"* ";
continue;
}
else
cout<<i%10<<' ';
}
cout<<endl;
cout<<"此时坐标为("<<n-tempx<<','<<m-tempy<<')'<<endl;
Sleep(1000);
markx=tempx;
marky=tempy;
step++;
//Sleep(5000);
}
}
int choiceforcontinue;
printf("如果您要继续测试，请输入1，退出请输入2:");
scanf("%d",&choiceforcontinue);
if(choiceforcontinue==1)
continue;
else
break;
}
//-----------------------------------------------------------------------------------------------------------------------//
else
{
printf("初始状态下，河南岸有%d个商人，%d个随从\n",n,m);
while(1)
{
//Sleep(5000);
if (flagforreturn==1)
{
if(markx==n&&marky==m)
break;
flagforreturn=2;
tempx=a[markx][marky].prex2;
tempy=a[markx][marky].prey2;
printf("第%d步：河南岸有%d个商人，%d个随从，此时，对岸有%d个商人，%d个随从（此时船在北岸）\n\n",step,n-tempx,m-tempy,tempx,tempy);
///////////////////////////////////////////////////////////////////////////////////正确性检测/////////////////////////////////////////////////////////////////////////////////////
/* if(tempx==0||tempx==n||(tempx>=tempy&&n-tempx>=m-tempy)&&(n-markx+m-marky>n-tempx+m-tempy))
cout<<"此步正确"<<endl;
else
cout<<"此步错误"<<endl;*///
////////////////////////////////////////////////////////////////////////////////////////正确性检测/////////////////////////////////////////////////////////////////////////////////////
markx=tempx;
marky=tempy;
step++;
//Sleep(5000);
}
else if(flagforreturn==2)
{
if(markx==n&&marky==m)
break;
flagforreturn=1;
tempx=a[markx][marky].prex1;
tempy=a[markx][marky].prey1;
printf("第%d步：河南岸有%d个商人,%d个随从，此时，对岸有%d个商人，%d个随从（此时船在南岸）\n\n",step,n-tempx,m-tempy,tempx,tempy);
////////////////////////////////////////////////////////////////////////////////////////正确性检测/////////////////////////////////////////////////////////////////////////////////////
/* if(tempx==0||tempx==n||(tempx>=tempy&&n-tempx>=m-tempy)&&(n-markx+m-marky<n-tempx+m-tempy))
cout<<"此步正确"<<endl;
else
cout<<"此步错误"<<endl;*/
////////////////////////////////////////////////////////////////////////////////////////正确性检测/////////////////////////////////////////////////////////////////////////////////////
markx=tempx;
marky=tempy;
step++;
//Sleep(5000);
}
}
int choiceforcontinue;
printf("如果您要继续测试，请输入1，退出请输入2:");
scanf("%d",&choiceforcontinue);
if(choiceforcontinue==1)
continue;
else
break;
}
}
//////////////////////////////////////////////////以上为动画演示及文字演示部分////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////以下是结束动画部分/////////////////////////////////////////////////////////////////////////////
N=20;
while(N--)
{
system("cls");
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" 谢谢您的使用！再见！ "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" · "<<endl;
cout<<" "<<endl;
cout<<" · "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
Sleep(10);
system("cls");
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" 谢谢您的使用！再见！ "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" │ "<<endl;
cout<<" ＼ ／ "<<endl;
cout<<" ─ ─ │ "<<endl;
cout<<" ／ ＼ ＼ ／ "<<endl;
cout<<" │ ─ ─ "<<endl;
cout<<" ／ ＼ "<<endl;
cout<<" │ "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
Sleep(10);
system("cls");
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" 谢谢您的使用！再见！ "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" │ "<<endl;
cout<<" ＼ ／ "<<endl;
cout<<" │ "<<endl;
cout<<" ─ ─ ＼ ／ "<<endl;
cout<<" "<<endl;
cout<<" ／ ＼ ─ ─ "<<endl;
cout<<" │ "<<endl;
cout<<" ／ ＼ "<<endl;
cout<<" │ "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
Sleep(10);
system("cls");
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" 谢谢您的使用！再见！ "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
Sleep(10);
}
system("pause");
return 0;
}