USACO-Section1.5 Mother's Milk （深度优先搜索）

2017-8-1

题目描述

给你三个容器，初始时前两个为空，最后一个为满，理想状态下，求当第一个容器 为空时，最后一个容器所剩的所有可能性

解答

(1)只能有牛奶的倒给未满的 (2)避免陷入死循环->记录出现过的情况

代码

/* ID: 18795871 PROG: milk3 LANG: C++ */ #include<iostream> #include<cstring> #include<fstream> using namespace std;ifstream fin("milk3.in"); ofstream fout("milk3.out");const int N = 20; int a,b,c; int f[N+1]; int d[N+1][N+1];void dfs(int x,int y,int z){int t;d[x][y]=1;if (x==0){f[z]=1;}if (x>0&&y!=b){t=min(x,b-y);if (!d[x-t][y+t]) dfs(x-t,y+t,z);}if (x>0&&z!=c){t=min(x,c-z);if (!d[x-t][y]) dfs(x-t,y,z+t);}if (y>0&&x!=a){t=min(a-x,y);if (!d[x+t][y-t]) dfs(x+t,y-t,z);}if (y>0&&z!=c){t=min(c-z,y);if (!d[x][y-t]) dfs(x,y-t,z+t);}if (z>0&&x!=a){t=min(a-x,z);if (!d[x+t][y]) dfs(x+t,y,z-t);}if (z>0&&y!=b){t=min(b-y,z);if (!d[x][y+t]) dfs(x,y+t,z-t);} }int main() { memset (f,0,sizeof(f));memset (d,0,sizeof(d));fin>>a>>b>>c;dfs(0,0,c);int i,j,s1=0,s2=0;for (i=0;i<=N;i++){if (f[i]) s1++;}for (i=0;i<=N;i++){if (f[i]){fout<<i<<" ";s2++;}if (s2==s1-1) break;}for (j=i+1;j<=N;j++){if (f[j]){fout<<j<<endl;break; }}return 0; }

一共有6种可能出现的倾倒情况，但是只能由有牛奶的倒给未满的，并且每次要不倒满，要不倒空，深搜即可，需要注意以下几点：
（1）为了避免来回倒：a -> b，b -> a，我们需要记录出现过的情况，不然递归结束不了。
（2）本来想用set来着，但是结构体作为set元素会比较复杂，还得在结构体里面重写一个函数。
（3）出现过的状态必须是三种情况完全相同。
然后我用了一个很蠢的方法：

if (x[10000*a+100*b+c]) return ;x[10000*a+100*b+c]=true;

注意不可以在if判断里面写，要不然一下子就结束了。

/* ID: 18795871 PROG: milk3 LANG: C++ */ #include<iostream> #include<cstring> #include<fstream> #include<set> using namespace std;ifstream fin("milk3.in"); ofstream fout("milk3.out");const int N = 20; bool f[N+1],x[202030]; int A,B,C;void dfs(int a,int b,int c){if (a==0){f[c]=true;}if (x[10000*a+100*b+c]) return ;x[10000*a+100*b+c]=true;int tmp;if (a>0&&b!=B){tmp=min(a,B-b);dfs(a-tmp,b+tmp,c);} if (b>0&&a!=A){tmp=min(A-a,b);dfs(a+tmp,b-tmp,c);} if (a>0&&c!=C){tmp=min(a,C-c);dfs(a-tmp,b,c+tmp);} if (c>0&&a!=A){tmp=min(c,A-a);dfs(a+tmp,b,c-tmp);} if (b>0&&c!=C){tmp=min(b,C-c);dfs(a,b-tmp,c+tmp);} if (c>0&&b!=B){tmp=min(c,B-b);dfs(a,b+tmp,c-tmp);} }int main(){while (fin>>A>>B>>C){memset(f,false,sizeof(f));memset(x,false,sizeof(x));dfs(0,0,C);int i,j,cnt=0,p=0;for (i=0;i<=C;i++){if (f[i]) cnt++;}for (i=0;i<=C;i++){if (f[i]){p++;fout<<i<<" ";}if (p==cnt-1) break;}for (j=i+1;j<=C;j++){if (f[j]){fout<<j<<endl;break;}}}return 0; }

其实不难发现，其实它们三个容器中的牛奶总和是一定的，那么我们只要将a和b进行标记就可以了，如果a和b相同的话，那么c自然就相同了。那么我们只要用二维数组就可以标记某一种出现的情况了。没有像上面一样浪费那么多空间。

/* ID: 18795871 PROG: milk3 LANG: C++ */ #include<iostream> #include<cstring> #include<fstream> #include<set> using namespace std;ifstream fin("milk3.in"); ofstream fout("milk3.out");const int N = 20; bool f[N+1],x[N+1][N+1]; int A,B,C;void dfs(int a,int b,int c){if (a==0){f[c]=true;}if (x[a][b]) return ;x[a][b]=true;int tmp;if (a>0&&b!=B){tmp=min(a,B-b);dfs(a-tmp,b+tmp,c);} if (b>0&&a!=A){tmp=min(A-a,b);dfs(a+tmp,b-tmp,c);} if (a>0&&c!=C){tmp=min(a,C-c);dfs(a-tmp,b,c+tmp);} if (c>0&&a!=A){tmp=min(c,A-a);dfs(a+tmp,b,c-tmp);} if (b>0&&c!=C){tmp=min(b,C-c);dfs(a,b-tmp,c+tmp);} if (c>0&&b!=B){tmp=min(c,B-b);dfs(a,b+tmp,c-tmp);} }int main(){while (fin>>A>>B>>C){memset(f,false,sizeof(f));memset(x,false,sizeof(x));dfs(0,0,C);int i,j,cnt=0,p=0;for (i=0;i<=C;i++){if (f[i]) cnt++;}for (i=0;i<=C;i++){if (f[i]){p++;fout<<i<<" ";}if (p==cnt-1) break;}for (j=i+1;j<=C;j++){if (f[j]){fout<<j<<endl;break;}}}return 0; } 新人创作打卡挑战赛发博客就能抽奖！定制产品红包拿不停！

总结

以上是生活随笔为你收集整理的USACO-Section1.5 Mother's Milk （深度优先搜索）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。