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: 646956
UserID: handsomecui
Submit time: 2015-12-10 20:23:59
Language: C++
Length: 1393 Bytes.
Result: Accepted #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
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<Node>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<j)continue;
if(b.ns&&b.ns<b.nw)continue;
if(a.ns-i<a.nw-j&&(a.ns-i))continue;
if(vis[b.r][b.ns][b.nw])continue;
// printf("%d %d\n",i,j);
if(b.ns==x&&b.nw==y&&b.r==1){
printf("%d\n",b.t);
return;
}
vis[b.r][b.ns][b.nw]=1;
dl.push(b);
}
}
}
puts("-1");return;
}
int main(){
int x,y,n;
while(~scanf("%d%d%d",&x,&y,&n)){
bfs(x,y,n);
}
return 0;
}