FZU 2188 BFS

最多只有200个羊，200狼，所以最多只有200*200种状态

再加上题上的限制条件,不管在任何地方，羊的个数不能少于狼，除非羊为0，可以剪枝掉大量状态

所以对所有情况进行BFS即可

要注意一些判定条件

1：不管在左岸还是右岸或船上，羊的个数不能少于狼，除非羊为0

2：起始时，若狼的个数大于羊，则无解（注意数据存在没有羊只有狼的情况）

3：在移动中直接判断状态是否合法，能提供大量剪枝

#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;

struct node
{
    int x,y,t,s;
};

int used[210][210][2],x,y,n;
int bfs()
{
    queue<node>q;
    node cur,next;
    int i,j,tx,ty;
    if (x<y && x!=0) return -1;
    cur.x=x;
    cur.y=y;
    cur.t=0;
    cur.s=0;
    memset(used,0,sizeof(used));
    used[x][y][0]=1; // 0 代表当前人在左岸，1代表在右岸
    q.push(cur);

    while (!q.empty())
    {
        cur=q.front();
        q.pop();
        if (cur.s==0)
        {

        for (i=0;i<=n && i<=cur.x;i++)
            for (j=0;j<=cur.y && (j<=i || i==0) ;j++)
            {
                if (i+j==0) continue;
                if (i+j>n) break; // 狼+羊大于船载量
                if (cur.x-i<cur.y-j && cur.x-i!=0) continue; // 移动后原来岸上羊<狼
                tx=x-cur.x;
                ty=y-cur.y;
                if (tx+i<ty+j && tx+i!=0) continue; // 移动后对面岸上羊<狼
                next.x=cur.x-i;
                next.y=cur.y-j;
                next.s=1;
                if (used[next.x][next.y][1]==0)
                {
                    used[next.x][next.y][1]=1;
                    next.t=cur.t+1;
                    if (next.x==0 && next.y==0)
                        return next.t;
                    q.push(next);
                }
            }
        }
        else
        {


        tx=x-cur.x;
        ty=y-cur.y;
        for (i=0;i<=n && i<=tx;i++)
            for (j=0;(j<=i || i==0)  && j<=ty;j++)
            {
                if (i+j==0) continue;
                if (i+j>n) break;
                if (tx-i<ty-j&& tx-i!=0) continue;
                next.x=cur.x+i;
                next.y=cur.y+j;
                next.s=0;
                if (next.x<next.y && next.x!=0) continue;
                if (used[next.x][next.y][0]==0)
                {
                    used[next.x][next.y][0]=1;
                    next.t=cur.t+1;
                    q.push(next);
                }

            }
        }
    }
    return -1;
}
int main()
{
    while (scanf("%d%d%d",&x,&y,&n)!=EOF)
    {
        printf("%d\n",bfs());
    }
    return 0;
}

FZU 2188 BFS

原文：http://blog.csdn.net/u011932355/article/details/44538887