windows下Dev解10l7l3l倒水

题面:一个容积10L的水桶装满水,还有二个7L、3L的水桶无水,水不能倒到别的地方,要让10L的水桶里有5L水最少倒几次

需求:给大一学弟学妹讲解广度优先搜索

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int b[3][100005];
int stime=0; //数字越大.休眠时间越久
int m=0,i,j;
int time1=107,time2=103,time3=710,time4=73,time5=37,time6=310;
int head=1,tail=2,btime=0,bord;
void zzzz(){
_sleep(stime*1000); //休眠时间单位ms
printf("\n\t%d\t%d\t%d\n",b[0][i],b[1][i],b[2][i]);
printf("%d\t%d\t%d\t%d\n",btime, b[0][tail-1],b[1][tail-1],b[2][tail-1]);
if(b[1][tail-1]==5){ m=1;}
}
int main()
{
b[0][0]=10; b[1][0]=7; b[2][0]=3;
b[0][1]=10; b[1][1]=0; b[2][1]=0;
//三杯子,初始只有10L的杯子是满的
// b[0][1]=1; b[1][1]=0; b[2][1]=0;
//三杯子,初始10L的杯子是满的
while(head<tail){
if(m==1) break;
btime++;
bord=tail;
for(i=head;i<bord;i++){
printf("\n%d\t%d\t%d\t%d\n",btime, b[0][i],b[1][i],b[2][i]);
if(m==1) break;
//找到55平分则退出
if(b[0][i]!=0){
//如果10L的杯子有酒
if(b[1][i]<7){
//如果7L的杯子没满
if(b[0][i]+b[1][i]<7){
//如果10L和7L杯子加起来不能补满7L的杯子
b[0][tail]=0;
b[1][tail]=b[1][i]+b[0][i];
//全倒入7L杯子
b[2][tail]=b[2][i];
zzzz();
}
else{
//如果10L和7L杯子加起来补满7L的杯子
b[0][tail]=b[1][i]+b[0][i]-7;
b[1][tail]=7;
//7L杯子补满
b[2][tail]=b[2][i];
tail++;
zzzz();
}
}
if(b[2][i]<3){
//如果3L的杯子没满
if(b[0][i]+b[2][i]<3){
//如果10L和3L杯子加起来不能补满3L的杯子
b[0][tail]=0;
b[1][tail]=b[1][i];
b[2][tail]=b[2][i]+b[0][i];
//全倒入3L杯子
tail++;
zzzz();
}
else{ //如果10L和3L杯子加起来补满3L的杯子
b[0][tail]=b[2][i]+b[0][i]-3;
b[1][tail]=b[1][i];
b[2][tail]=3;
//3L杯子补满
tail++;
zzzz();
}
}
} //10-7 10-3
if(b[1][i]!=0){
//如果7L的杯子有酒
if(b[0][i]<10){
//如果10L的杯子没满
if(b[0][i]+b[1][i]<b[0][0]){
//如果10L和7L杯子加起来不能补满10L的杯子
b[0][tail]=b[1][i]+b[0][i];
b[1][tail]=0;
b[2][tail]=b[2][i];
tail++;
zzzz();
}
else{
//如果10L和7L杯子加起来补满10L的杯子
b[0][tail]=10;
b[1][tail]=b[1][i]+b[0][i]-10;
b[2][tail]=b[2][i];
tail++;
zzzz();
}
}
if(b[2][i]<3){
//如果3L的杯子没满
if(b[1][i]+b[2][i]<3){
//如果7L和3L杯子加起来不能补满3L的杯子
b[0][tail]=b[0][i];
b[1][tail]=0;
b[2][tail]=b[2][i]+b[1][i];
tail++;
zzzz();
}
else{ //如果7L和3L杯子加起来补满3L的杯子
b[0][tail]=b[0][i];
b[1][tail]=b[1][i]+b[2][i]-3;
b[2][tail]=3;
tail++;
zzzz();
}
}
} //7-10 7-3
if(b[2][i]!=0){
//如果3L的杯子有酒
if(b[0][i]<10){
//如果10L的杯子没满
if(b[0][i]+b[2][i]<10){
//如果10L和3L杯子加起来不能补满10L的杯子
b[0][tail]=b[2][i]+b[0][i];
b[1][tail]=b[1][i];
b[2][tail]=0;
tail++;
zzzz();
}
else{ //如果10L和3L杯子加起来能补满3L的杯子
b[0][tail]=10;
b[1][tail]=b[1][i];
b[2][tail]=b[0][i]+b[2][i]-10;
tail++;
zzzz();
}
}
if(b[1][i]<7){
//如果7L的杯子没满
if(b[2][i]+b[1][i]<7){
//如果3L和7L杯子加起来不能补满7L的杯子
b[0][tail]=b[0][i];
b[1][tail]=b[1][i]+b[2][i];
b[2][tail]=0;
tail++;
zzzz();
}
else{
//如果3L和7L杯子加起来补满7L的杯子
b[0][tail]=b[0][i];
b[1][tail]=7;
b[2][tail]=b[2][i]+b[1][i]-7;
tail++;
zzzz();
}
}
} //3-7 3-10
}
head=bord;
}
if(m==1) printf("\n%d\t%d\t%d\t%d\n",m, b[0][i-1],b[1][i-1],b[2][i-1]);
}

 

剪枝优化

windows下Dev解10l7l3l倒水

上一篇:TypeScript vs. C#: LINQ


下一篇:BZOJ 1061: [Noi2008]志愿者招募 费用流