过河

Problem Description

一天，小明需要把x只羊和y只狼运输到河对面。船可以容纳n只动物和小明。每次小明划船时，都必须至少有一只动物来陪他，不然他会感到厌倦，不安。不论是船上还是岸上，狼的数量如果超过羊，狼就会把羊吃掉。小明需要把所有动物送到对面，且没有羊被吃掉，最少需要多少次他才可以穿过这条河？
Input

有多组数据，每组第一行输入3个整数想x, y, n (0≤ x, y,n ≤ 200)
Output

如果可以把所有动物都送过河，且没有羊死亡，则输出一个整数：最少的次数。否则输出 -1 .
Sample Input

3 3 233 33 3
Sample Output

11-1

http://blog.csdn.net/yanghui07216/article/details/50195997

#include<stdio.h>  
#include<string.h>  
#include<queue>  
#include<algorithm>  
using namespace std;  
struct zz  
{  
    int a;  
    int b;  
    int l;//表次数   
    int w;//表位置   
}p,d;  
int n,m,mm,flag;  
int v[2][210][210];  
void bfs(int x,int y)  
{  
    p.a=x;p.b=y;p.l=0;p.w=0;//初始化羊和狼全部在0号岸  
    queue<zz>q;  
    q.push(p);  
    int i,j;  
    while(!q.empty())  
    {  
        p=q.front();  
        q.pop();  
        if(p.a==n&&p.b==m&&p.w==1)//满足条件  
        {  
            flag=1;  
            printf("%d\n",p.l);  
            return ;  
        }  
        d.l=p.l+1;//次数  
        d.w=p.w==1?0:1;//改变岸  
        for(i=0;i<=p.a;i++)  
        {  
            for(j=0;j<=p.b;j++)  
            {  
                if(i+j==0)//没有带羊或者狼  
                    continue;  
                if(i+j>mm)//带的动物超出上限  
                    continue;  
                if(i<j&&i!=0)//带的羊少于狼 ，注意，此时羊的数量不为0  
                    continue;  
                if(p.a-i<p.b-j&&p.a-i!=0)//带走后剩下的羊数量少于狼  
                    continue;  
                d.a=n-p.a+i;//将要带过去的岸的羊和狼的数量   
                d.b=m-p.b+j;  
                if(d.a<d.b&&d.a!=0)//如果带过去后羊的数量少于狼  
                    continue;  
                if(v[d.w][d.a][d.b])//如果此方案使用过  
                    continue;  
                v[d.w][d.a][d.b]=1;//标记此方案使用过  
                q.push(d);  
            }  
        }  
    }  
    printf("-1\n");  
}   
int main()  
{  
    while(scanf("%d%d%d",&n,&m,&mm)!=EOF)  
    {  
        flag=0;  
        memset(v,0,sizeof(v));  
        v[0][n][m]=1;  
        bfs(n,m);  
    }  
    return 0;  
}