#include<stdio.h>
unsigned?short?temp[20];//存儲中間狀態
int?step?=?0;//
char?OP[][16]={
"初始狀態", "A全倒給B", "A全倒給C", "A倒滿B", "A倒滿C", "B全倒給A", "B全倒給C", "B倒滿C", "C全倒給A", "C全倒給B", "C倒滿B"};
//輸出步驟
void?display()
{
int?i; for(i=0;i<=step;i++)printf("%2d:[?%10s?]?:?%d,%d,%d\n",
? i+1,
? OP[(temp[i]&0xf000)>>12],
? (temp[i]&0xf00)>>8,
? (temp[i]&0xf0)>>4,
? temp[i]&0xf);
}
//檢查是否會出現重復狀態
int?check()
{
int?i; for(i=0;i<step;i++) {if((temp[step]&0x0fff)==(temp[i]&0x0fff))?return?1;
} return?0;}
//遞歸函數
//A,B,C分別是3個油桶當前有多少油，op是倒油的具體操作
int?foo(int?A12,int?B9,?int?C5,?int?op)
{
temp[step]=(op<<12)|(A12<<8)|(B9<<4)|C5; if(check()==1)?return?0; if(A12==6?&&?B9==6)?return?1; step++; //A12全部倒給B9 if(A12?&&?(A12+B9<=9)?&&?foo(0,A12+B9,C5,1))?return?1; //A12全部倒給C5 else?if(A12?&&?(A12+C5<=5)?&&?foo(0,B9,A12+C5,2))?return?1; //A12倒滿B9 else?if(A12?&&?(A12+B9>9)?&&? foo(A12+B9-9,9,C5,3))?return?1; //A12倒滿C5 else?if(A12?&&?(A12+C5>5)?&&?foo(A12+C5-5,B9,5,4))?return?1; //B9全部倒給A12 else?if(B9?&&?(B9+A12<12)?&&?foo(A12+B9,0,C5,5))?return?1; //B9全部倒給C5 else?if(B9?&&?(B9+C5<=5)?&&?foo(A12,0,B9+C5,6))?return?1; //B9倒滿C5 else?if(B9?&&?(B9+C5>5)?&&?foo(A12,B9+C5-5,5,7))?return?1; //C5全部倒給A12 else?if(C5?&&?(C5+A12<12)?&&?foo(C5+A12,B9,0,8))?return?1; //C5全部倒給B9 else?if(C5?&&?(C5+B9<=9)?&&?foo(A12,B9+C5,0,9))?return?1; //C5倒滿B9 else?if(C5?&&?(C5+B9>9)?&&?foo(A12,9,C5+B9-5,10))?return?1; else {step--;
return?0;
}}
int?main()
{
if(foo(12,0,0,0))?display();}
結果：