过河（bfs）-白红宇

过河（bfs）

阅读量：5732 次

发布时间：2019-06-18

本文共 1681 字，大约阅读时间需要 5 分钟。

Problem 2188 过河I

Accept: 112 Submit: 277 Time Limit: 3000 mSec Memory Limit : 32768 KB

Problem Description

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

Input

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

Output

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

Sample Input

      3   3   2 33  33  3 

Sample Output

      11 -1 

Hint

第一个样例

次数船方向左岸右岸（狼羊）

0： 0 0 3 3 0 0

1： 2 0 > 1 3 2 0

2： 1 0 < 2 3 1 0

3： 2 0 > 0 3 3 0

4： 1 0 < 1 3 2 0

5： 0 2 > 1 1 2 2

6： 1 1 < 2 2 1 1

7： 0 2 > 2 0 1 3

8： 1 0 < 3 0 0 3

9： 2 0 > 1 0 2 3

10： 1 0 < 2 0 1 3

11： 2 0 > 0 0 3 3

题解：用bfs遍历每种情况，结构体存放岸上的羊和狼的状态，应该从结点出发，下一个结点对应上一个结点

RunID: 646956UserID: handsomecuiSubmit time: 2015-12-10 20:23:59Language: C++Length: 1393 Bytes.Result: Accepted#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             using namespace std;const int INF=0x3f3f3f3f;const double PI=acos(-1.0);typedef long long LL;#define mem(x,y) memset(x,y,sizeof(x))#define PI(x) printf("%d",x)#define PL(x) printf("%lld",x)#define SI(x) scanf("%d",&x)#define SL(x) scanf("%lld",&x)#define P_ printf(" ")#define T_T while(T--)struct Node{ int nw,ns,r,t;};int vis[2][210][210];void bfs(int x,int y,int n){ queue
              
               dl; mem(vis,0); Node a,b; a.ns=x;a.nw=y;a.t=0;a.r=0; dl.push(a); vis[0][x][y]=1; int cur=0; while(!dl.empty()){ a=dl.front(); dl.pop(); // printf("/******/\n"); for(int i=0;i<=a.ns;i++){ for(int j=0;j<=a.nw;j++){ b.ns=x-a.ns+i; b.nw=y-a.nw+j; b.t=a.t+1; b.r=a.r^1; if(i+j==0)continue; if(i+j>n)continue; if(i&&i

转载地址：http://dflwx.baihongyu.com/

你可能感兴趣的文章