Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
1A is supposed to post code for memorize..#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator