【BFS】poj 3414 Pots

题目描述：

http://poj.org/problem?id=3414

 

中文大意：

使用两个锅，盛取定量水。

两个锅的容量和目标水量由用户输入。

允许的操作有：灌满锅、倒光锅内的水、一个锅中的水倒入另一个锅。

在两个锅互相倒水的过程中，若一个锅被倒满，而原来的锅中还有水，则剩余在原来的锅中。

不断执行这三个过程，直到任意一个锅中，贮存了目标数量的水，过程结束。

 

思路：

队列节点记录的是当前两个锅的贮水量和之前的一系列操作。

弹出队列首节点，获取到当前两个锅的贮水信息后，可以有 6 种操作：

　　FILL(1)、FILL(2)、DROP(1)、DROP(2)、POUR(1,2)、POUR(2,1)。

过程中需要用到数组 visited[105][105]，用来记录当前情况是否出现过。

若不使用 visited 数组进行剪枝，则会出现超时的情况。

 

代码：

#include<iostream>
#include<queue>
#include<string>
using namespace std;

int a,b,c; 

struct node{
    int x,y;
    vector<string> msg;
    node(int x, int y, vector<string> msg){
        this->x = x;
        this->y = y;
        this->msg = msg;
    };
    node(int x, int y){
        this->x = x;
        this->y = y;
    };
};

bool visited[105][105] = {false};

void bfs(){
    node start = node(0, 0);
    node next = node(0, 0);
    
    visited[0][0] = true;
    
    queue<node> q;
    q.push(start);
    
    while(!q.empty()){
        start = q.front();
        q.pop();
        
        if(start.x == c || start.y == c){
            int n = start.msg.size();
            printf("%d
", n);
            
            for(int i=0;i<n;i++){
                cout<<start.msg[i]<<endl;
            }
            return;
        }
        
        //FILL(1)
        next = node(a, start.y, start.msg);
        if(!visited[next.x][next.y]){
            visited[next.x][next.y] = true;
            
            next.msg.push_back("FILL(1)");
            q.push(next);
        }

        //FILL(2)
        next = node(start.x, b, start.msg);
        if(!visited[next.x][next.y]){
            visited[next.x][next.y] = true;
            
            next.msg.push_back("FILL(2)");
            q.push(next);
        }
        
        //DROP(1)
        next = node(0, start.y, start.msg);
        if(!visited[next.x][next.y]){
            visited[next.x][next.y] = true;

            next.msg.push_back("DROP(1)");
            q.push(next);
        }
        
        //DROP(2)
        next = node(start.x, 0, start.msg);
        if(!visited[next.x][next.y]){
            visited[next.x][next.y] = true;

            next.msg.push_back("DROP(2)");
            q.push(next);
        }
        
        //POUR(1,2)
        int fill_num = b - start.y;
        if(start.x >= fill_num){
            next = node(start.x - fill_num, b, start.msg);
            if(!visited[next.x][next.y]){
                visited[next.x][next.y] = true;

                next.msg.push_back("POUR(1,2)");
                q.push(next);
            }
        }
        else{
            next = node(0, start.y + start.x, start.msg);
            if(!visited[next.x][next.y]){
                visited[next.x][next.y] = true;
                
                next.msg.push_back("POUR(1,2)");
                q.push(next);
            }
        }
        
        //POUR(2,1)
        fill_num = a - start.x;
        if(start.y >= fill_num){
            next = node(a, start.y - fill_num, start.msg);
            if(!visited[next.x][next.y]){
                visited[next.x][next.y] = true;

                next.msg.push_back("POUR(2,1)");
                q.push(next);
            }
        }
        else{
            next = node(start.x + start.y, 0, start.msg);
            if(!visited[next.x][next.y]){
                visited[next.x][next.y] = true;
                
                next.msg.push_back("POUR(2,1)");
                q.push(next);
            }
        }
    }
    printf("impossible
");
}

int main(){ 
    scanf("%d %d %d", &a, &b, &c);
    bfs();
}