倒水问题 POJ 1606 自己的解法好慢的说。

#include<iostream>
using namespace std;
//============================================
int A,B,res,t;
int vis[1000][1000];
int path[1000];
int minpath[1000];
int minstep=10000;
char p[6][20]={"fill A","fill B","empty A","empty B","pour A B","pour B A"};
bool Search(int a,int b,int order)
{
if(vis[a][b]==1)return 0;
if(b==res)
{
if(order<minstep)
{
memcpy(&minpath,&path,sizeof(path));
}
return 1;
}
     vis[a][b]=1;
   if(a<A)
{
path[order]=1;
   if(Search(A,b,order+1))//==fill A
{
   return 1;
}
  }
if(b<B)
{
path[order]=2;
   if(Search(a,B,order+1))//==fill B
{
   return 1;
}
}
if(a>0&&a<=A)
{
path[order]=3;
if(Search(0,b,order+1))//==empty A
{
return 1;
}
}
if(b>0&&b<=B)
{
path[order]=4;
if(Search(a,0,order+1))//==empty B
{
return 1;
}
}
if(a>0&&a<=A&&b<B)
{
path[order]=5;
       if(Search(max(0,a+b-B),min(a+b,B),order+1))//==pour A into B
{
   return 1;
}
}
if(b>0&&b<=B&&a<A)
{
path[order]=6;
if(Search(min(a+b,A),max(0,a+b-A),order+1))//==pour B into A
{
   return 1;
}
vis[a][b]=0;
return 0;
}
}
int main()
{
//freopen("E:/ACM/in.txt", "r", stdin);
while(cin>>A>>B>>res)
{
memset(vis,0,sizeof(vis));
memset(path,0,sizeof(path));
memset(minpath,0,sizeof(minpath));
if(Search(0,0,1))
{
int i=1,m;
while(minpath[i]!=0)
{
i++;
}
m=i;
       for(i=1;i<m;++i)
{
cout<<p[minpath[i]-1]<<endl;
}
cout<<"success"<<endl;
}
}
return 0;
}

posted on 2011-09-15 20:24 四也 阅读(218) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2011年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜