Pots POJ - 3414(bfs + 记录路径)

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <queue>
  5 #include <stack>
  6 #include <algorithm>
  7 #include <cmath>
  8 #include <map>
  9 #define mem(a,b) memset(a,b,sizeof(a));
 10 using namespace std;
 11 #define INF 0x3f3f3f3f
 12 typedef long long ll;
 13 int dir[4][2] = {0,1,0,-1,1,0,-1,0};
 14 const int maxn = 2005;
 15 int a,b,c,d,dd;
 16 struct Node {
 17     int x,y,fa,ans,num,type;
 18     Node(){};
 19     Node(int xx,int yy,int faa,int aans,int nnum,int t1):x(xx),y(yy),fa(faa),ans(aans),num(nnum),type(t1){};
 20 }p[maxn];
 21 stack<int>m;
 22 bool vis[205][205],flag;
 23 void bfs(int ea,int eb) {
 24     queue<Node>q;
 25     q.push(Node(0,0,0,0,0,0));
 26     vis[ea][eb] = 1;
 27     p[0].x = ea,p[0].y = eb,p[0].fa = 0,p[0].ans = 0,p[0].num = 0,p[0].type = 0;
 28    int t = 0;
 29     while(!q.empty()) {
 30         Node temp = q.front();
 31         q.pop();
 32         if(temp.x == c || temp.y == c) {
 33             flag = 1;
 34             d = temp.ans;
 35             dd = temp.num;
 36             break;
 37         }
 38         int fx,fy,ra,rb;
 39         //操作１A给Ｂ
 40         rb = b - temp.y;
 41         if(temp.x > rb) {
 42             ra = temp.x - rb;
 43             fx = ra;
 44             fy = b;
 45 
 46         }
 47         else {
 48             ra = 0;
 49             fx = ra;
 50             fy = temp.x + temp.y;
 51         }
 52         if(!vis[fx][fy]){
 53         t++;
 54         vis[fx][fy] = 1;
 55         p[t].x = fx,p[t].y = fy,p[t].fa = temp.num,p[t].num = t,p[t].type = 1,p[t].ans = temp.ans+1;
 56         q.push(Node(p[t].x,p[t].y,p[t].fa,p[t].ans,p[t].num,p[t].type));
 57         }
 58 
 59         //操作２　Ｂ给Ａ
 60         ra = a - temp.x;
 61         if(temp.y > ra) {
 62             rb = temp.y - ra;
 63             fy = rb;
 64             fx = a;
 65         }
 66         else {
 67             rb = 0;
 68             fy = rb;
 69             fx = temp.x + temp.y;
 70         }
 71         if(!vis[fx][fy]){
 72         t++;
 73         vis[fx][fy] = 1;
 74         p[t].x = fx,p[t].y = fy,p[t].fa = temp.num,p[t].num = t,p[t].type = 2,p[t].ans = temp.ans+1;
 75         q.push(Node(p[t].x,p[t].y,p[t].fa,p[t].ans,p[t].num,p[t].type));
 76         }
 77 
 78         //操作３ Ｂ倒完
 79         fx = temp.x , fy = 0;
 80         if(!vis[fx][fy]){
 81         t++;
 82         vis[fx][fy] = 1;
 83         p[t].x = fx,p[t].y = fy,p[t].fa = temp.num,p[t].num = t,p[t].type = 3,p[t].ans = temp.ans+1;
 84         q.push(Node(p[t].x,p[t].y,p[t].fa,p[t].ans,p[t].num,p[t].type));
 85         }
 86 
 87         //操作４　Ａ倒完
 88         fy = temp.y , fx = 0;
 89         if(!vis[fx][fy]){
 90         t++;
 91         vis[fx][fy] = 1;
 92         p[t].x = fx,p[t].y = fy,p[t].fa = temp.num,p[t].num = t,p[t].type = 4,p[t].ans = temp.ans+1;
 93         q.push(Node(p[t].x,p[t].y,p[t].fa,p[t].ans,p[t].num,p[t].type));
 94         }
 95 
 96         //操作５　Ｂ倒满
 97         fx = temp.x , fy = b;
 98         if(!vis[fx][fy]){
 99         t++;
100         vis[fx][fy] = 1;
101         p[t].x = fx,p[t].y = fy,p[t].fa = temp.num,p[t].num = t,p[t].type = 5,p[t].ans = temp.ans+1;
102         q.push(Node(p[t].x,p[t].y,p[t].fa,p[t].ans,p[t].num,p[t].type));
103         }
104 
105         //操作6  A倒满
106         fx = a, fy = temp.y;
107         if(!vis[fx][fy]){
108         t++;
109         vis[fx][fy] = 1;
110         p[t].x = fx,p[t].y = fy,p[t].fa = temp.num,p[t].num = t,p[t].type = 6,p[t].ans = temp.ans+1;
111         q.push(Node(p[t].x,p[t].y,p[t].fa,p[t].ans,p[t].num,p[t].type));
112         }
113 
114     }
115 }
116 int main()
117 {
118     cin >> a >> b >> c;
119     bfs(a,b);
120     if(flag == 1) {
121         cout << d << endl;
122         int t = dd,tt;
123         m.push(p[t].type);
124         while(1){
125             t = p[t].fa;
126             tt = p[t].num;
127             if(tt == 0)
128                 break;
129             m.push(p[tt].type);
130         }
131         while(!m.empty()){
132             t = m.top();
133             m.pop();
134             if(t == 1) {
135                 cout << "POUR(1,2)" << endl;
136             }
137             else if(t == 2)
138                 cout << "POUR(2,1)" << endl;
139             else if(t == 3)
140                 cout << "DROP(2)" << endl;
141             else if(t == 4)
142                 cout << "DROP(1)" << endl;
143             else if(t == 5)
144                 cout << "FILL(2)" << endl;
145             else if(t == 6)
146                 cout << "FILL(1)" << endl;
147         }
148     }
149     else {
150         cout << "impossible" << endl;
151     }
152     return 0;
153 }