2017-8-1

題目描述

給你三個(gè)容器，初始時(shí)前兩個(gè)為空，最后一個(gè)為滿，理想狀態(tài)下，求當(dāng)?shù)谝粋€(gè)容器 為空時(shí)，最后一個(gè)容器所剩的所有可能性

解答

(1)只能有牛奶的倒給未滿的 (2)避免陷入死循環(huán)->記錄出現(xiàn)過(guò)的情況

代碼

/* 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種可能出現(xiàn)的傾倒情況，但是只能由有牛奶的倒給未滿的，并且每次要不倒?jié)M，要不倒空，深搜即可，需要注意以下幾點(diǎn)：
（1）為了避免來(lái)回倒：a -> b，b -> a，我們需要記錄出現(xiàn)過(guò)的情況，不然遞歸結(jié)束不了。
（2）本來(lái)想用set來(lái)著，但是結(jié)構(gòu)體作為set元素會(huì)比較復(fù)雜，還得在結(jié)構(gòu)體里面重寫(xiě)一個(gè)函數(shù)。
（3）出現(xiàn)過(guò)的狀態(tài)必須是三種情況完全相同。
然后我用了一個(gè)很蠢的方法：

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

注意不可以在if判斷里面寫(xiě)，要不然一下子就結(jié)束了。

/* 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; }

其實(shí)不難發(fā)現(xiàn)，其實(shí)它們?nèi)齻€(gè)容器中的牛奶總和是一定的，那么我們只要將a和b進(jìn)行標(biāo)記就可以了，如果a和b相同的話，那么c自然就相同了。那么我們只要用二維數(shù)組就可以標(biāo)記某一種出現(xiàn)的情況了。沒(méi)有像上面一樣浪費(fèi)那么多空間。

/* 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; } 新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的USACO-Section1.5 Mother's Milk （深度优先搜索）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。