http://acm.fzu.edu.cn/problem.php?pid=2188

过河I

Time Limit:3000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

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

分析:

次数   羊    狼   方向   羊     狼

0;  3  3  0  0  0

1;  3  1  1  0  2

2;  3  2  0  0  1

3;  3  0  1  0  3

4;  3  1  0  0  2

5:  1  1  1  2  2

6:    2  2  0  1  1

7;  0  2  1  3  1

8;  0  3  0  3  0

9;  0  1  1  3  2

10;  0  2  0  3  1

11;  0  0  1  3  3

题目中有多个减枝描述;

“船可以容纳n只动物” && “至少有一只动物来陪他” && “不论是船上还是岸上,狼的数量如果超过羊,狼就会把羊吃掉 ”  && “0≤ x, y,n ≤ 200”。

AC代码:

 #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
bool vis[][][];
int sx,sy,n;
struct node
{
int x,y;
int c;
int cnt;
};
node cur,nxt;
queue<node> que;
int main()
{
while(~scanf("%d%d%d",&sx,&sy,&n))
{
memset(vis,,sizeof(vis));
while(!que.empty()) que.pop();
cur.x=sx,cur.y=sy;
cur.c=,cur.cnt=;// cur.c = 0 代表左岸 , cur.c = 1 代表右岸 , cur.cnt 代表步数。
vis[sx][sy][] = ;
//vis[x][y][2] 表示船到达0或1岸后,此岸上的羊数x,和狼数y , 标记数组。
que.push(cur);
bool flag=;
while(!que.empty())
{
cur=que.front();
que.pop();
if(cur.c==&&cur.x==sx&&cur.y==sy)
{
flag=true;
printf("%d\n",cur.cnt);
break;
}
nxt.c=!cur.c;
nxt.cnt=cur.cnt+;
for(int i=;i<=cur.x;i++)// i 代表船上羊的数量。
for(int j=;j<=cur.y;j++)// j 代表船上狼的数量。
{
if(i+j==) continue;
if(i+j>n) continue;
if(i<j&&i!=) continue;
if(cur.x-i<cur.y-j&&cur.x-i!=) continue;
nxt.x=sx-cur.x+i,nxt.y=sy-cur.y+j;
if(nxt.x<nxt.y&&nxt.x!=) continue;
if(vis[nxt.x][nxt.y][nxt.c]) continue;
vis[nxt.x][nxt.y][nxt.c]=;
que.push(nxt);
}
}
if(!flag) puts("-1");
}
return ;
}
05-02 08:45