bfs+哈希表 + 三杯水

給出三個水杯，大小不一，並且只有最大的水杯的水是裝滿的，其余兩個為空杯子。三個水杯之間相互倒水，並且水杯沒有標識，只能根據給出的水杯體積來計算。現在要求你寫出一個程序，使其輸出使初始狀態到達目標狀態的最少次數。
輸入
第一行一個整數N(0<N<50)表示N組測試數據
接下來每組測試數據有兩行，第一行給出三個整數V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三個水杯的體積。
第二行給出三個整數E1 E2 E3 （體積小於等於相應水杯體積）表示我們需要的最終狀態
輸出
每行輸出相應測試數據最少的倒水次數。如果達不到目標狀態輸出-1

#include<string.h>

#include<stdlib.h>
#include<ctype.h>
#include<stdio.h>
int visit[100][100][100];  //記錄出現過的狀態
int dis[1000];     //記錄每種狀態時候，到了多少次水
int p[3];     //三瓶水的容量
int a[1000][3];   //倒水狀態
int goal[3];     //目標狀態
void visited(int tmp[3]);
int check(int tmp[3]);
bool pour(int tmp[3],int i,int j)
{
if(tmp[i] ==0)return false;      //瓶子沒有水了
if(tmp[j] == p[j]) return false;    //另一個瓶子裝滿了水
if(tmp[i] > (p[j]-tmp[j]))
{
tmp[i]-= (p[j]-tmp[j]);
tmp[j] = p[j];
}
else
{
tmp[j] +=tmp[i];
tmp[i] =0;
}
if(check(tmp))
{
return false;
}
else
{
visited(tmp);
return true;
}
}

int check(int tmp[3])   //查看是否出現過狀態
{
if(visit[tmp[0]][tmp[1]][tmp[2]])
return 1;
return 0;
}

void visited(int tmp[3])   //記錄這種狀態出現過
{
visit[tmp[0]][tmp[1]][tmp[2]] = 1;
}

int bfs()
{
int i,j,k;
int head=0,tail=1;
visited(a[head]);   //記錄初始狀態為出現過
while(head <tail)
{
for(i=0;i<3;i++)
if(a[head][i]!=goal[i]) break;
if(i>=3)
return dis[head];    //與目標狀態相同
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
for(k=0;k<3;k++)      //查看第i層的下一個節點狀態
a[tail][k] = a[head][k];
if(j!=i)
if(pour(a[tail],i,j))
{
dis[tail] = dis[head]+1;
tail++;     //入隊列
}
}
head++;   //出隊列
}
return -1;
}
int main()
{
int count[100];
int n;
scanf("%d",&n);
int i=-1;
while(++i<n)
{
memset(a,0,sizeof(a));
memset(dis,0,sizeof(dis));
memset(visit,0,sizeof(visit));

scanf("%d %d %d",&p[0],&p[1],&p[2]);
scanf("%d %d %d",&goal[0],&goal[1],&goal[2]);
a[0][0] = p[0];

int min=bfs();
count[i] = min;
}
for(i=0;i<n;i++)
printf("%d\n",count[i]);
return 1;
}