利用广度策略解决农夫过河问题

系统管理员 2022-11-21 09:58 187阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]  
一.基本思路：  
1.初始状态0000入队  
2.当队列不空且没有到达结束状态1111时循坏以下操作：  
①队头状态出队  
②按照农夫一个人走、农夫分别带上三个走循坏以下操作：  
~如果农夫和他们在同一岸，则计算新的状态。  
~如果新状态是安全的并且是没有处理过的，则更新status\[\],并将新状态入队。  
③当状态为1111时逆向输出status\[\]数组。  
二.需要注意的时状态能否入队，要判断以下3条，满足一条件均不能入队。  
①不可能：通过判断是否在统一对岸。  
②不安全：通过安全函数判断。  
③处理过：记录处理过的状态。

代码及注释如下

#include <stdio.h>
    #include <stdlib.h>
    typedef char DataType;
    struct Queue
    { 
    	int Max;
    	int f;
    	int r;
    	DataType *elem;
    };
    typedef struct Queue *SeqQueue;
    
    SeqQueue SetNullQueue_seq(int m)
    { 
    	SeqQueue squeue;
    	squeue = (SeqQueue)malloc(sizeof(struct Queue));
    	if (squeue == NULL)
    	{ 
    		printf("Alloc failure\n");
    		return NULL;
    	}
    	squeue->elem = (int*)malloc(sizeof(DataType)*m);
    	if (squeue->elem != NULL)
    	{ 
    		squeue->Max = m;
    		squeue->f = 0;
    		squeue->r = 0;
    		return squeue;
    	}
    }
    
    int IsNullQueue_seq(SeqQueue squeue)
    { 
    	return (squeue->f == squeue->r);
    }
    void EnQueue_seq(SeqQueue squeue,DataType x)
    { 
        if((squeue->r+1)%squeue->Max==squeue->f)
            printf("It is FULL Queue!");
        else
        { 
            squeue->elem[squeue->r]=x;
            squeue->r=(squeue->r+1)%squeue->Max;
        }
    }
    void DeQueue_seq(SeqQueue squeue)
    { 
        if(IsNullQueue_seq(squeue)==1)
            printf("it is empty queue!");
        else
        { 
            squeue->f=(squeue->f+1)%(squeue->Max);
    
        }
    }
    DataType FrontQueue_seq(SeqQueue squeue)
    { 
        if(IsNullQueue_seq(squeue)==1)
        { 
            printf("It is empty queue");
            return 33;
        }
        else
        { 
            return squeue->elem[squeue->f];
        }
    
    }
    //***************************************
    int FarmerOnRight(int status)//判断当前条件下农夫的位置
    { 
        return(0!=(status&0x08));
    }
    int WorfOnRight(int status)//判断当前位置下狼的位置
    { 
        return(0!=(status&0x04));
    }
    int CabbageOnRight(int status)//判断当前位置下白菜的位置
    { 
        return(0!=(status&0x02));
    }
    int GoatOnRight(int status)//判断当前位置下羊是否在南岸
    { 
        return(0!=(status&0x01));
    }
    int IsSafe(int status)//判断当前位置下羊是否安全
    { 
        if((GoatOnRight(status)==CabbageOnRight(status))&&(GoatOnRight(status)!=FarmerOnRight(status)))
            return 0;//羊吃白菜
        if((GoatOnRight(status)==WorfOnRight(status))&&(GoatOnRight(status)!=FarmerOnRight(status)))
            return 0;狼吃羊
        return 1;//其他状态时安全的
    }
    void FarmerRiver()
    { 
        int i,movers,nowstatus,newstatus;
        int status[16];//用于记录已考虑的状态路径
        SeqQueue moveTo;//用于记录可以安全到达的中间状态
        moveTo=SetNullQueue_seq(20);//创建空队列
        EnQueue_seq(moveTo,0x00);//初始状态时所有物品在南岸
        for(i=0;i<16;i++)//数组status初始化位-1
            status[i]=-1;
        status[0]=0;
        while(!IsNullQueue_seq(moveTo)&&(status[15]==-1))
        //队列非空且没有到达结束状态
        { 
            nowstatus=FrontQueue_seq(moveTo);//取队头状态为当前状态
            DeQueue_seq(moveTo);
            for(movers=1;movers<=8;movers<<=1)//遍历三个要移动的物品
            //考虑各种物品移动
                if((0!=(nowstatus&0x08))==(0!=(nowstatus&movers)))
                //考虑农夫与移动的物品在同一侧
            { 
                newstatus=nowstatus^(0x08|movers);//计算新状态
                //如果新状态时安全的且之前没有出现过
                if(IsSafe(newstatus)&&(status[newstatus]==-1))
                { 
                    status[newstatus]=nowstatus;//记录新状态
                    EnQueue_seq(moveTo,newstatus);//新状态入队
                }
            }
        }
        //输出经过的装态路径
        if(status[15]!=-1)//到达最终状态
        { 
            printf("the reverse path is:\n");
            for(nowstatus=15;nowstatus>=0;nowstatus=status[nowstatus])
            { 
                printf("The nowstatus is:%d\n",nowstatus);
                if(nowstatus==0)
                    return;
            }
    
        }
        else
            printf("No solution.\n");//问题无解
    
    }
    int main()
    { 
        FarmerRiver();
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/45c720578d1646e4b65effa331bde049.png