The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1606-Jugs

本题的题意大致是:给你两个容器,指定它们的容量Ca,Cb,还有一个目标容量N;
两个容器初始含水量都是零,问如何配制出容量为N的液体;

我的做法很简单 BFS搜索,不过代码实在太长   在网上搜了一下 居然有一个500+B的代码 看得不是很明白 希望有牛人能够指点一下

//This is the source code for Problem POJ 1606
#include<iostream>
#include
<cmath>
#include
<cstring>
#include
<stack>
using namespace std;



struct node 
{
    
    
int ca;
    
int cb;
    
int pre;
}
line[100];
int hash[10000];
stack
<node>mystack;





int main()
{
    
    
int a,b,c;
    
int front;
    
int rear;
    
while(scanf("%d%d%d",&a,&b,&c)!=EOF)
    
{
        memset(hash,
0,sizeof(hash));
        
while(mystack.empty()!=true)
            mystack.pop();

        
        node temp;
        temp.ca
=0;
        temp.cb
=0;
        temp.pre
=-1;
        line[
1]=temp;
        front
=1;
        rear
=1;
        
while(front<=rear)
        
{
        
            
if(line[front].ca==c||line[front].cb==c)
                
break;
            
else if(line[front].ca!=a)
            
{
                node temp;
                temp.ca
=a;
                temp.cb
=line[front].cb;
                temp.pre
=front;
                
//给出下一个状态
                int hashnum=temp.ca*10+temp.cb;
                
if(hash[hashnum]==0)
                
{
                    hash[hashnum]
=1;
                    rear
++;
                    line[rear]
=temp;
                }
//判重

                
                
            }

            
if(line[front].cb!=b)
            
{
                
                node temp;
                temp.cb
=b;
                temp.ca
=line[front].ca;
                temp.pre
=front;
                
//给出下一个状态
                int hashnum=temp.ca*10+temp.cb;
                
if(hash[hashnum]==0)
                
{
                    hash[hashnum]
=1;
                    rear
++;
                    line[rear]
=temp;
                }
//判重
            
            }

            
if(line[front].ca!=0)
            
{
                
                node temp;
                temp.ca
=0;
                temp.cb
=line[front].cb;
                temp.pre
=front;
                
//给出下一个状态
            

                
int hashnum=temp.ca*10+temp.cb;
                
if(hash[hashnum]==0)
                
{
                    hash[hashnum]
=1;
                    rear
++;
                    line[rear]
=temp;
                }
//判重
                
            }

            
if(line[front].cb!=0)
            
{
                
                node temp;
                temp.cb
=0;
                temp.ca
=line[front].ca;
                temp.pre
=front;
                
//给出下一个状态


                
int hashnum=temp.ca*10+temp.cb;
                
if(hash[hashnum]==0)
                
{
                    hash[hashnum]
=1;
                    rear
++;
                    line[rear]
=temp;
                }
//判重
            
            }




            
if(line[front].ca!=0&&line[front].cb!=b)
            
{
                
                node temp;
    
                
if(b-line[front].cb>=line[front].ca)
                
{
                    temp.ca
=0;
                    temp.cb
=line[front].cb+line[front].ca;
                    temp.pre
=front;
                }

                
else
                
{
                    temp.ca
=line[front].ca-(b-line[front].cb);
                    temp.cb
=b;
                    temp.pre
=front;
                }


                
//给出下一个状态
                
                
                
int hashnum=temp.ca*10+temp.cb;
                
if(hash[hashnum]==0)
                
{
                    hash[hashnum]
=1;
                    rear
++;
                    line[rear]
=temp;
                }
//判重
                
            }




            
if(line[front].ca!=a&&line[front].cb!=0)
            
{
                
                node temp;
                
                
if(a-line[front].ca>=line[front].cb)
                
{
                    temp.cb
=0;
                    temp.ca
=line[front].ca+line[front].cb;
                    temp.pre
=front;
                }

                
else
                
{
                    temp.cb
=line[front].cb-(a-line[front].ca);
                    temp.ca
=a;
                    temp.pre
=front;
                }

                
                
//给出下一个状态
                
                
                
int hashnum=temp.ca*10+temp.cb;
                
if(hash[hashnum]==0)
                
{
                    hash[hashnum]
=1;
                    rear
++;
                    line[rear]
=temp;
                }
//判重
                
            }

            front
++;
        }


        
int tempnum=front;
        
while(line[tempnum].pre!=-1)
        
{

            mystack.push(line[tempnum]);
            tempnum
=line[tempnum].pre;
        }

        node tempnode1;
        tempnode1.ca
=0;
        tempnode1.cb
=0;
        tempnode1.pre
=-1;

        node tempnode2;

        
while(mystack.empty()!=true)
        
{
            tempnode2
=mystack.top();
            mystack.pop();
            
if(tempnode1.ca!=0&&tempnode2.ca==0&&(tempnode1.cb==tempnode2.cb))
                printf(
"empty A\n");
            
else if(tempnode1.cb!=0&&tempnode2.cb==0&&(tempnode1.ca==tempnode2.ca))
                printf(
"empty B\n");
            
else if(tempnode1.ca!=a&&tempnode2.ca==a&&(tempnode1.cb==tempnode2.cb))
                printf(
"fill A\n");
            
else if(tempnode1.cb!=b&&tempnode2.cb==b&&(tempnode1.ca==tempnode2.ca))
                printf(
"fill B\n");
            
else if(tempnode2.ca>tempnode1.ca)
                printf(
"pour B A\n");
            
else 
                printf(
"pour A B\n");
            tempnode1
=tempnode2;
        }

        printf(
"success\n");
    }

    
return 0;
}




500B的代码如下:
#include<iostream>
using namespace std;
int main()
{
int ca,cb,n;
int a,b;
while(cin>>ca>>cb>>n)
{
    a
=0;b=0;
while(1)
{
    
if(b==cb) {cout<<"empty B"<<endl;b=0;if(b==n) {cout<<"success"<<endl;break;}}
    
else if(a==0{cout<<"fill A"<<endl;a=ca;if(b==n) {cout<<"success"<<endl;break;}}
    
else if(b+a<cb) {cout<<"pour A B"<<endl;b=b+a;a=0;if(b==n) {cout<<"success"<<endl;break;}}
    
else if(b+a>=cb) {cout<<"pour A B"<<endl;a=a+b-cb;b=cb;if(b==n) {cout<<"success"<<endl;break;}}
}

}

system(
"pause");
return 0;
}

希望大家能给我解释一下 多谢^_^

posted on 2009-07-06 16:38 abilitytao 阅读(482) 评论(1)  编辑 收藏 引用

评论

# re: POJ 1606-Jugs 2010-11-20 16:33 天青色~~

学长还有1天告别acm,这个东东还需要人来解释吗?呵呵^_^
因为这题是special judge,有多解,所以直接模拟……  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理