早知道要寫這么長 就用類寫了 呵呵
//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;
}