农夫1.c

农夫 狼 羊 菜 过河 问题 sdfd

/*农夫与狼，羊，菜 */
#include "stdio.h"
#include "conio.h"
#define MAX 16
int sta[4]={0,0,0,0};
int path[MAX];
char *s[]={"Farmer","Sheep","Wolf","Vegetable"};
void main()
  { 
  	 int i,passok(int);
  	 void  output(int);
  	    for(i=0;i<MAX;i++) path[i]=-1;
  	    i=1;
  	    while(1)/*回溯找路径*/
  	       {
  	       	  path[i]++;
  	       	  if (path[i]>3)
  	       	     {
  	       	     	if (i<2) break;
  	       	     	i--;continue;
  	       	     }
  	       	  if (passok(i))
  	       	     {  
  	       	     	if (sta[0]+sta[1]+sta[2]+sta[3]==4) output(i);
      	     	    else i++; 
  	       	     }   
  	       }
  }

int passok(int i)/*判断当前方案能否通过*/
  { 
  	 int t;
  	 	
  	 	t=path[i];
  	 	if (sta[t]!=sta[0]||path[i]==path[i-1]) return 0;
  	 	sta[0]^=1;
  	    if (t) sta[t]^=1;
  	    if (!(sta[1]==sta[2]&&sta[1]!=sta[0]||sta[1]==sta[3]&&sta[1]!=sta[0])) return 1;
  	    sta[0]^=1;
  	    if (t) sta[t]^=1;
  	    return 0;
  } 

void output(int n)/*输出过河方案*/
  {   
  	 int t,i,j,k,x,flag;
  	    sta[0]=sta[1]=sta[2]=sta[3]=0;
  	    clrscr();flag=1,x=20;
  	    for(i=1;i<=n;i++)
  	       {
  	       	  sta[0]^=1;
  	       	  t=path[i];
  	       	  if (t) sta[t]^=1;
  	       	  if (sta[0]) flag=1,x=20;
  	       	  else flag=-1,x=60;   
  	       	  for(j=0;j<40;j++)
  	       	     {
  	       	         gotoxy(x+flag*j,8+2*t);
  	       	         printf("%s",s[t]);	
  	       	         gotoxy(x+flag*j,8);
  	       	         printf("%s",s[0]);
  	       	         for(k=0;k<4;k++)
  	       	            {  if (!k||k==t) continue;  
  	       	               gotoxy(20+40*sta[k],8+2*k);
  	       	               printf("%s",s[k]);	
  	       	            }	
  	       	         delay(60000);
  	       	         clrscr();   
  	       	     }
  	       }
  }