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;
}
补充：软件开发 , C++ ,
