http://poj.org/problem?id=3414bfs:都是些基本的算法了，各种bfs写了不少啦。
这个题目也挺简单的，主要是那几个转移方向还是要优化下好写，觉得自己写得还可以哈：
嘿嘿：
bfs:0ms
#include<stdio.h>
#include<string.h>
#include<math.h>
int a[2],c,head,tail;
int que[10005][2],pre[10005],p[10005],vis[105][105],ans[10005];
int check()
{
if (que[tail][0]==c||que[tail][1]==c)
return 1;
return 0;
}
int Fill(int i)
{
int t=tail+1;
que[t][0]=que[head][0];
que[t][1]=que[head][1];
que[t][i-1]=a[i-1];
if (!vis[que[t][0]][que[t][1]])
{
vis[que[t][0]][que[t][1]]=1;
p[t]=i;
pre[t]=head;
return 1;
}
return 0;
}
int Drop(int i)
{
int t=tail+1;
que[t][0]=que[head][0];
que[t][1]=que[head][1];
que[t][i-1]=0;
if (!vis[que[t][0]][que[t][1]])
{
vis[que[t][0]][que[t][1]]=1;
p[t]=2+i;
pre[t]=head;
return 1;
}
return 0;
}
int Four(int i,int j)
{
int min,t=tail+1;
min=(que[head][i-1])<(a[j-1]-que[head][j-1])?(que[head][i-1]):(a[j-1]-que[head][j-1]);
que[t][j-1]=que[head][j-1]+min;
que[t][i-1]=que[head][i-1]-min;
if (!vis[que[t][0]][que[t][1]])
{
vis[que[t][0]][que[t][1]]=1;
p[t]=4+i;
pre[t]=head;
return 1;
}
return 0;
}
int bfs()
{
int i,tmp;
memset(vis,0,sizeof(vis));
head=0;
tail=1;
que[1][0]=0;
que[1][1]=0;
vis[0][0]=1;
pre[1]=0;
p[1]=0;
while (head<tail)
{
head++;
tmp=1;
for (i=1; i<=2 ; i++ )
{
if (Fill(i))
tail++;
if (check())
return tail;
if (Drop(i))
tail++;
if (check())
return tail;
if (Four(i,i+tmp))
tail++;
if (check())
return tail;
tmp=-1;
}
}
return 0;
}
int print(int k)
{
int i;
if (!k)
{
printf("impossible\n");
return 0;
}
i=0;
while (k)
{
ans[++i]=p[k];
k=pre[k];
}
printf("%d\n",i-1);
for (k=i-1; k>=1 ; k-- )
{
if (ans[k]<=2)
{
printf("FILL(%d)\n",ans[k]);
continue;
}
if (ans[k]<=4)
{
printf("DROP(%d)\n",ans[k]-2);
continue;
}
if (ans[k]==5)
printf("POUR(1,2)\n");
else
printf("POUR(2,1)\n");
}
return 0;
}
int main()
{
int k;
scanf("%d%d%d",&a[0],&a[1],&c);
if (c>a[0]&&c>a[1])
k=0;
else
k=bfs();
print(k);
return 0;
}
这几天的bfs，dfs，都是第一次就AV，挺爽的，嘿嘿。
多写写恶心的代码，以后就不恶心了，哈哈。
很纳闷，那些用很少内存的是怎么做到的呢？看来自己还是很弱啊～～～