Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

1A is supposed to post code for memorize..

Posted by zqg_test at 2015-06-17 14:03:02 on Problem 3414
#include<iostream>
#include<queue>
#include<stack>
#include<fstream>
using namespace std;

int A,B,C;

struct Node{
    int i;
    int j;
    int step;
};

struct Trace{
    Node n;
    Node ori;
    int op; // 0:f1,1;f2,2:d1,3:d3,4:p1,5:p2
};

int map[200][200]={0};
Trace Nmap[200][200];
queue<Node> q;
stack<Trace> s;

void Fill1(Node *n){
    n->i = A;
}
void Fill2(Node *n){
    n->j = B;
}
void Drop1(Node *n){
    n->i = 0;
}
void Drop2(Node *n){
    n->j = 0;
}
void Pour1(Node *n){
    if(n->i == 0 || n->j == B){
        return;
    }
    if(n->i > B-(n->j)){
        n->i = n->i - (B-(n->j));
        n->j = B;
    }
    if(n->i <= B-(n->j)){
        n->j = n->j + n->i;
        n->i = 0;
    }
}
void Pour2(Node *n){
    if(n->j == 0 || n->i == A){
        return;
    }
    if(n->j > A-(n->i)){
        n->j = n->j - (A-(n->i));
        n->i = A;
    }
    if(n->j <= A-(n->i)){
        n->i = n->i + n->j;
        n->j = 0;
    }
}

void insert(Node n , Node ori, int op){
    if(map[n.i][n.j] == 1){
        return;
    }
    else{
        n.step++;
        q.push(n);
        map[n.i][n.j] = 1;
        Nmap[n.i][n.j].n = n;
        Nmap[n.i][n.j].ori = ori;
        Nmap[n.i][n.j].op = op;
        return;
    }
}

void backtrack(Node n){
    Node temp;
    temp = Nmap[n.i][n.j].ori;
    s.push(Nmap[n.i][n.j]);
    while(1){
        temp = Nmap[n.i][n.j].ori;
        if(temp.i == 0 && temp.j == 0){
            break;
        }
        else{
            s.push(Nmap[temp.i][temp.j]);
            n = temp;
        }
    }
    while(!s.empty()){
        Trace t;
        t = s.top();
        switch (t.op){
            case 0: cout<< "FILL(1)"<<endl; break;
            case 1: cout<< "FILL(2)"<<endl; break;
            case 2: cout<< "DROP(1)"<<endl; break;
            case 3: cout<< "DROP(2)"<<endl; break;
            case 4: cout<< "POUR(1,2)"<<endl; break;
            case 5: cout<< "POUR(2,1)"<<endl; break;
        }
        s.pop();
    }
}

int main(){
    cin>>A>>B>>C;
    Node n;
    n.i = 0;
    n.j = 0;
    n.step = 0;
    q.push(n);
    int i,j;
    for(i=0;i<200;i++){
        for(j=0;j<200;j++){
            map[i][j]=0;
            Nmap[i][j].n = n;
            Nmap[i][j].ori = n;
            Nmap[i][j].op = -1;
        }
    }
    while(!q.empty()){
        Node temp,ori;
        ori = q.front();
        temp = q.front();
        if(temp.i == C || temp.j == C){
            cout<<temp.step<<endl;
            backtrack(temp);
            return 0;
        }
        if(temp.i != A){
            Fill1(&temp);
            insert(temp,ori,0);
        }
        temp = q.front();
        if(temp.j != B){
            Fill2(&temp);
            insert(temp,ori,1);
        }
        temp = q.front();
        if(temp.i != 0){
            Drop1(&temp);
            insert(temp,ori,2);
        }
        temp = q.front();
        if(temp.j != 0){
            Drop2(&temp);
            insert(temp,ori,3);
        }
        temp = q.front();
        Pour1(&temp);
        insert(temp,ori,4);
        temp = q.front();
        Pour2(&temp);
        insert(temp,ori,5);
        q.pop();
    }
    cout<<"impossible"<<endl;
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator