97 七區資訊學科能力競賽 97七區資訊學科3(改編)
作法 : DFS
我個人認為多重解不夠多
硬湊到AC (程式碼1)
程式碼2(WA) 但是我認為這比較好
/**********************************************************/
#include <stdlib.h>
#include <stdio.h>
int GCD(int a,int b)
{
int temp;
while(a%b)
{
temp=a;
a=b;
b=temp%b;
}
return b;
}
int steps[10000][2],ans[10000][2],min;
int record[201][201];
int Ca,Cb,N,find=0;
void WaterJug(int now,int Ca,int Cb,int A,int B,int goal)
{
if(record[Ca][Cb]==1) return;
record[Ca][Cb]=1;
steps[now][0]=Ca;
steps[now][1]=Cb;
int a,b,c;
if(Ca+Cb==goal)
{
if(now<min)
{
for(a=1;a<=now;a++)
{
ans[a][0]=steps[a][0];ans[a][1]=steps[a][1];
}
min=now;
}
return;
}
if(Cb!=0)
{
WaterJug(now+1,Ca,0,A,B,goal);/*倒掉B*/
if(Ca!=A)
{/*將B倒入A*/
int temp=A-Ca;/*A剩餘容量*/
if(Cb>temp) /*B倒完還有剩*/
WaterJug(now+1,A,Cb-temp,A,B,goal);
else WaterJug(now+1,Ca+Cb,0,A,B,goal);
}
}
if(Ca!=0)
{
WaterJug(now+1,0,Cb,A,B,goal);/*倒掉A*/
if(Cb!=B)
{/*將A倒入B*/
int temp=B-Cb;/*B剩餘容量*/
if(Ca>temp) /*A倒完還有剩*/
WaterJug(now+1,Ca-temp,B,A,B,goal);
else WaterJug(now+1,0,Cb+Ca,A,B,goal);
}
}
if(Ca<A) /*裝滿A*/
WaterJug(now+1,A,Cb,A,B,goal);
if(Cb<B) /*裝滿B*/
WaterJug(now+1,Ca,B,A,B,goal);
}
main()
{
while(scanf("%d %d %d",&Ca,&Cb,&N)==3)
{
int a,b;
for(a=0;a<=200;a++)
for(b=0;b<=200;b++)
record[a][b]=0;
min=20000;
if(N%GCD(Ca,Cb)==0&&N<=Ca+Cb)
{
WaterJug(0,0,0,Ca,Cb,N);
printf("(0,0)");
for(a=1;a<=min;a++)
printf(" -> (%d,%d)",ans[a][0],ans[a][1]);
printf("\n");
}
else
printf("NO\n");
}
return 0;
}
/***************************************************/
#include <stdlib.h>
#include <stdio.h>
int GCD(int a,int b)
{
int temp;
while(a%b)
{
temp=a;
a=b;
b=temp%b;
}
return b;
}
int steps[10000][2],ans[10000][2],min;
int record[201][201];
int Ca,Cb,N,find=0;
void WaterJug(int now,int Ca,int Cb,int A,int B,int goal)
{
if(record[Ca][Cb]<now||now>min) return;
record[Ca][Cb]=now;
steps[now][0]=Ca;
steps[now][1]=Cb;
int a,b,c;
if(Ca+Cb==goal)
{
if(now<min)
{
for(a=1;a<=now;a++)
{
ans[a][0]=steps[a][0];ans[a][1]=steps[a][1];
}
min=now;
}
return;
}
if(Cb!=0)
{
WaterJug(now+1,Ca,0,A,B,goal);/*倒掉B*/
if(Ca!=A)
{/*將B倒入A*/
int temp=A-Ca;/*A剩餘容量*/
if(Cb>temp) /*B倒完還有剩*/
WaterJug(now+1,A,Cb-temp,A,B,goal);
else WaterJug(now+1,Ca+Cb,0,A,B,goal);
}
}
if(Ca!=0)
{
WaterJug(now+1,0,Cb,A,B,goal);/*倒掉A*/
if(Cb!=B)
{/*將A倒入B*/
int temp=B-Cb;/*B剩餘容量*/
if(Ca>temp) /*A倒完還有剩*/
WaterJug(now+1,Ca-temp,B,A,B,goal);
else WaterJug(now+1,0,Cb+Ca,A,B,goal);
}
}
if(Ca<A) /*裝滿A*/
WaterJug(now+1,A,Cb,A,B,goal);
if(Cb<B) /*裝滿B*/
WaterJug(now+1,Ca,B,A,B,goal);
}
main()
{
while(scanf("%d %d %d",&Ca,&Cb,&N)==3)
{
int a,b;
for(a=0;a<=Ca;a++)
for(b=0;b<=Cb;b++)
record[a][b]=150;
min=150;
if(N%GCD(Ca,Cb)==0&&N<=Ca+Cb)
{
WaterJug(0,0,0,Ca,Cb,N);
printf("(0,0)");
for(a=1;a<=min;a++)
printf(" -> (%d,%d)",ans[a][0],ans[a][1]);
printf("\n");
}
else
printf("NO\n");
}
return 0;
}