Problem 2188 过河I
Accept: 116 Submit: 281
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
Source
FOJ有奖月赛-2015年03月 因缺思婷。
#include <queue> #include <cstdio> #include <cstring> using namespace std; struct ZT{ int a, b, step, posi; }S, R, B; bool flag; int n, m, M, vis[2][220][220]; void Bfs(int x, int y){ memset(vis, 0, sizeof(vis)); S.a = x; S.b = y; S.posi = 0; S.step = 0; vis[0][x][y] = 1; queue<ZT> Q; Q.push(S); while(!Q.empty()){ R = Q.front(); Q.pop(); if(R.a == n && R.b == m && R.posi == 1){ flag = true; printf("%d ", R.step); return; } B.step = R.step + 1; B.posi = (R.posi==1?0:1); for(int i = 0; i <= R.a; i++) for(int j = 0; j <= R.b; j++){ if(i+j == 0) continue; if(i+j > M) continue; if(i < j && i != 0) continue; if(R.a - i < R.b - j && R.a-i != 0) continue; B.a = n - R.a + i; B.b = m - R.b + j; if(B.a < B.b && B.a != 0) continue; if(vis[B.posi][B.a][B.b]) continue; vis[B.posi][B.a][B.b] = 1; Q.push(B); } } } int main(){ while(scanf("%d%d%d", &n, &m, &M) != EOF){ flag = false; Bfs(n, m); if(!flag) printf("-1 "); } return 0; }