fzu 2188 過河I，fzu2188過河i
http://acm.fzu.edu.cn/problem.php?pid=2188
過河I
Time Limit:3000MS
Memory Limit:32768KB
64bit IO Format:%I64d & %I64u
Submit Status Practice FZU 2188
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代碼：
![]()
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<algorithm>
5 #include<queue>
6 using namespace std;
7 bool vis[210][210][2];
8 int sx,sy,n;
9 struct node
10 {
11 int x,y;
12 int c;
13 int cnt;
14 };
15 node cur,nxt;
16 queue<node> que;
17 int main()
18 {
19 while(~scanf("%d%d%d",&sx,&sy,&n))
20 {
21 memset(vis,0,sizeof(vis));
22 while(!que.empty()) que.pop();
23 cur.x=sx,cur.y=sy;
24 cur.c=0,cur.cnt=0;// cur.c = 0 代表左岸 ， cur.c = 1 代表右岸 ， cur.cnt 代表步數。
25 vis[sx][sy][0] = 1;
26 //vis[x][y][2] 表示船到達0或1岸後，此岸上的羊數x，和狼數y ， 標記數組。
27 que.push(cur);
28 bool flag=0;
29 while(!que.empty())
30 {
31 cur=que.front();
32 que.pop();
33 if(cur.c==1&&cur.x==sx&&cur.y==sy)
34 {
35 flag=true;
36 printf("%d\n",cur.cnt);
37 break;
38 }
39 nxt.c=!cur.c;
40 nxt.cnt=cur.cnt+1;
41 for(int i=0;i<=cur.x;i++)// i 代表船上羊的數量。
42 for(int j=0;j<=cur.y;j++)// j 代表船上狼的數量。
43 {
44 if(i+j==0) continue;
45 if(i+j>n) continue;
46 if(i<j&&i!=0) continue;
47 if(cur.x-i<cur.y-j&&cur.x-i!=0) continue;
48 nxt.x=sx-cur.x+i,nxt.y=sy-cur.y+j;
49 if(nxt.x<nxt.y&&nxt.x!=0) continue;
50 if(vis[nxt.x][nxt.y][nxt.c]) continue;
51 vis[nxt.x][nxt.y][nxt.c]=1;
52 que.push(nxt);
53 }
54 }
55 if(!flag) puts("-1");
56 }
57 return 0;
58 }
View Code
