FZU(2188):狼羊过河问题，状态转移，BFS求解

题目连接：

意思：中文题目，就是给定狼羊的数目，求最小运输量把狼和羊全部送到对岸，条件是，岸上和船上的羊不能少于狼的数目，且每次渡船至少有一只动物。无解则输出-1。

只要认真分析，还是能够想到状态转移方法的。

假设左岸分别有x,y只羊和狼，右岸分别有羊和狼m,n只，假设从左岸分别把羊狼转移p,q只到右岸，则必须满足一下条件：

x-p不为0时，x-p>=y-q；

m+p不为0时，m+p>=n+q；

p不为0时，p>=q；

这里需要注意的是，当x-p或m+q或p为0时，需要特殊处理，此时，狼可以为任意值（必须客观）不必大于羊的数目。

从右岸到左岸的思想差不多。

分析到此。

代码：

刚开始用BFS交，TLE了，然后改写双BFS，结果却是RE，仔细一看，居然是两次都交错题目了，真是汗颜啊！！！！

不过，这题用BFS和双BFS差距还是蛮大的，一个70ms+，一个达到了900ms+。

单向BFS：

#include<iostream>
#include<cstdio>
#include<sstream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<string>
#define LL __int64
#define INF 0xfffffff

using namespace std;

struct state{
    int x,y;//左岸羊狼的数目
    int m,n;//右岸羊狼的数目
    int step;//转移步数
};

int vis[220][220][2];//左岸状态标志，为什么是2呢？vis[x][y]有两种不同的值
                     //可能是从右岸转移到左岸后的x,y，也可能是从右岸转移到左岸
                     //后的x,y，这两者是不一样的
int X,Y,N;

void bfs(){
    queue<state> Q;
    Q.push((state){X,Y,0,0,0});
    vis[X][Y][0]=vis[X][Y][1]=1;
    while(!Q.empty()){
        state tp=Q.front();
        if(!tp.x && !tp.y){
            cout<<tp.step<<endl;
            return;
        }
        Q.pop();
        if(tp.step & 1){//从右岸到左岸
            for(int p=0;p<=min(N,tp.m);p++)//下面需要注意的是羊为0时，狼的数目的处理
                for(int q=0;!p && (q<=min(tp.n,N)) || p && q<=p && (p+q)<=min(tp.m+tp.n,N);q++){
                    if(p+q==0) continue;
                    int tx=tp.x+p,ty=tp.y+q,tm=tp.m-p,tn=tp.n-q;
                    //下面也得注意羊的数目为0时，狼的数目的处理
                    if(tm<0 || tn<0 || tm && tm<tn || tx&&tx<ty) continue;
                    if(!vis[tx][ty][1]){
                        vis[tx][ty][1]=1;
                        Q.push((state){tx,ty,tm,tn,tp.step+1});
                    }
                }
        }
        else{//从左岸到右岸
            for(int p=0;p<=min(N,tp.x);p++)
                for(int q=0;!p && (q<=min(N,tp.y)) || p && q<=p &&(p+q)<=min(N,tp.x+tp.y);q++){
                    if(p+q==0) continue;
                    int tx=tp.x-p,ty=tp.y-q,tm=tp.m+p,tn=tp.n+q;
                    if(tx<0 || ty<0 || tx && tx<ty || tm&&tm<tn) continue;
                    if(!vis[tx][ty][0]){
                        vis[tx][ty][0]=1;
                        Q.push((state){tx,ty,tm,tn,tp.step+1});
                    }
                }
        }
    }
    cout<<-1<<endl;
}

int main(){
//freopen("C:\Documents and Settings\All Users\桌面\in.txt","r",stdin);
    while(cin>>X)
    {
        cin>>Y>>N;
        memset(vis,0,sizeof(vis));
        bfs();
    }
    return 0;
}

双向BFS：