| 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 233 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
Source
FOJ有奖月赛-2015年03月
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
int a,b,loact,step;
}p,temp;
int m,n,M;
int vis[2][505][505];
void bfs(int x,int y)
{
queue<node>q;
p.a=x;
p.b=y;
p.loact=0;
p.step=0;
memset(vis,0,sizeof(vis));
vis[0][x][y]=1;
q.push(p);
while(!q.empty())
{
p=q.front();
q.pop();
if(p.a==n&&p.b==m&&p.loact==1)
{
printf("%d\n",p.step);
return ;
}
temp.loact=p.loact==1?0:1;
temp.step=p.step+1;
for(int i=0;i<=p.a;i++)
{
for(int j=0;j<=p.b;j++)
{
if(i+j==0)
continue;
if(i<j&&i!=0)
continue;
if(i+j>M)
continue;
if(p.a-i<p.b-j&&p.a-i!=0)
continue;
temp.a=n-p.a+i;
temp.b=m-p.b+j;
if(temp.a<temp.b&&temp.a!=0)
continue;
if(vis[temp.loact][temp.a][temp.b])
continue;
vis[temp.loact][temp.a][temp.b]=1;
q.push(temp);
}
}
}
printf("-1\n");
}
int main()
{
while(scanf("%d%d%d",&n,&m,&M)!=EOF)
{
bfs(n,m);
}
return 0;
}