好久没写解题报告了, 刚刚做了个bfs, 不管水不水, 写个吧。
题意:
有两个容器,容量分别是A,B,对它们有三个操作:充满, 倒空,从容器1倒到容器2或者反过来倒, 问至少要多少步骤, 让其中一个里面液体的体积达到C,并输出那些步骤。
分析:
这个嘛。。。。就是简单的BFS。 没话说。代码被我写脑残了,这么多,自己也看得晕死。 我发现我都不懂怎么写解题报告了。。。
#include <stdio.h>
struct str
{
int ab[2]; //两个容器分别剩多少
int op; //操作
int parm; //对哪个容器的操作
int pre; //前一步操作
}queue[101];
int mark[101][101];
int ans[101][2];
int ab[2], c;
struct str cur, tmp;
void print()
{
int i=0;
while(tmp.pre > 0)
{
ans[i][0] = tmp.op;
ans[i++][1] = tmp.parm;
tmp = queue[tmp.pre];
}
ans[i][0] = tmp.op;
ans[i++][1] = tmp.parm;
printf("%d\n", i);
for(i--; i>=0; i--)
{
switch(ans[i][0])
{
case 1:
printf("FILL(%d)\n", ans[i][1]);
break;
case 2:
printf("DROP(%d)\n", ans[i][1]);
break;
case 3:
printf("POUR(%d,%d)\n", ans[i][1], (ans[i][1]+1) % 3 == 0 ? 1 : 2);
break;
}
}
}
int main()
{
int rear, front, index=0, tmpp;
scanf("%d%d%d", &ab[0], &ab[1], &c);
if(c == 0)
{
printf("0\n");
return 0;
}
front = rear = 0;
queue[front].ab[0] = 0;
queue[front].ab[1] = 0;
queue[front].pre = 0;
front++;
mark[0][0] = 1;
while(rear < front)
{
cur = queue[rear++];
//fill(1)
tmp = cur;
tmp.ab[0] = ab[0];
if(tmp.ab[0] == c)
{
tmp.op = 1;
tmp.parm = 1;
tmp.pre = rear-1;
print();
return 0;
}
else if(mark[tmp.ab[0]][tmp.ab[1]] == 0)
{
tmp.op = 1;
tmp.parm = 1;
tmp.pre = rear-1;
queue[front++] = tmp;
mark[tmp.ab[0]][tmp.ab[1]] = 1;
}
//fill(2)
tmp = cur;
tmp.ab[1] = ab[1];
if(tmp.ab[1] == c)
{
tmp.op = 1;
tmp.parm = 2;
tmp.pre = rear-1;
print();
return 0;
}
else if(mark[tmp.ab[0]][tmp.ab[1]] == 0)
{
tmp.op = 1;
tmp.parm = 2;
tmp.pre = rear-1;
queue[front++] = tmp;
mark[tmp.ab[0]][tmp.ab[1]] = 1;
}
//drop(1)
tmp = cur;
tmp.ab[0] = 0;
if(mark[tmp.ab[0]][tmp.ab[1]] == 0)
{
tmp.pre = rear-1;
tmp.parm = 1;
tmp.op = 2;
queue[front++] = tmp;
mark[tmp.ab[0]][tmp.ab[1]] = 1;
}
//drop(2)
tmp = cur;
tmp.ab[1] = 0;
if(mark[tmp.ab[0]][tmp.ab[1]] == 0)
{
tmp.pre = rear-1;
tmp.parm = 2;
tmp.op = 2;
queue[front++] = tmp;
mark[tmp.ab[0]][tmp.ab[1]] = 1;
}
//pour(2, 1);
tmp = cur;
if(tmp.ab[0] + tmp.ab[1] >= ab[0])
{
tmpp = tmp.ab[0];
tmp.ab[0] = ab[0];
tmp.ab[1] = tmpp+tmp.ab[1]-ab[0];
}
else
{
tmp.ab[0] += tmp.ab[1];
tmp.ab[1] = 0;
}
if(tmp.ab[0] == c || tmp.ab[1] == c)
{
tmp.op = 3;
tmp.parm = 2;
tmp.pre = rear-1;
print();
return 0;
}
else if(mark[tmp.ab[0]][tmp.ab[1]] == 0)
{
tmp.op = 3;
tmp.parm = 2;
tmp.pre = rear-1;
queue[front++] = tmp;
mark[tmp.ab[0]][tmp.ab[1]] = 1;
}
// pour(1, 2);
tmp = cur;
if(tmp.ab[0] + tmp.ab[1] >= ab[1])
{
tmpp = tmp.ab[1];
tmp.ab[1] = ab[1];
tmp.ab[0] = tmp.ab[0]+tmpp-ab[1];
}
else
{
tmp.ab[1] += tmp.ab[0];
tmp.ab[0] = 0;
}
if(tmp.ab[0] == c || tmp.ab[1] == c)
{
tmp.op = 3;
tmp.parm = 1;
tmp.pre = rear-1;
print();
return 0;
}
else if(mark[tmp.ab[0]][tmp.ab[1]] == 0)
{
tmp.op = 3;
tmp.parm = 1;
tmp.pre = rear-1;
queue[front++] = tmp;
mark[tmp.ab[0]][tmp.ab[1]] = 1;
}
}
printf("impossible\n");
return 0;
}
|
阅读(1626) | 评论(0) | 转发(0) |