| ||||||||||
| 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