POJ 3414 Pots bfs打印方案

很好玩的一个题。关键是又16ms 1A了，没有debug的日子才是好日子。。
  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <queue>
  4 #include <algorithm>
  5 #include <stack>
  6 using namespace std;
  7 int a, b, c;
  8 bool vis[110][110];
  9 enum Ways{FILL_A, FILL_B, DROP_A, DROP_B, POUR_AB, POUR_BA};
 10 
 11 struct Path
 12 {
 13     int px, py;
 14     Ways way;
 15 }path[110][110];
 16 
 17 struct status
 18 {
 19     int x, y, step;
 20 };
 21 
 22 void print_path(int x, int y)
 23 {
 24     stack<struct Path>s;
 25     while(!(x == 0 && y == 0))
 26     {
 27         s.push(path[x][y]);
 28         int tx = path[x][y].px;
 29         int ty = path[x][y].py;
 30         x = tx;
 31         y = ty;
 32     }
 33     while(!s.empty())
 34     {
 35         switch(s.top().way)
 36         {
 37             case FILL_A: printf("FILL(1)
");break;
 38             case FILL_B: printf("FILL(2)
");break;
 39             case DROP_A: printf("DROP(1)
");break;
 40             case DROP_B: printf("DROP(2)
");break;
 41             case POUR_AB: printf("POUR(1,2)
");break;
 42             case POUR_BA: printf("POUR(2,1)
");break;
 43         }
 44         s.pop();
 45     }
 46 }
 47 
 48 queue<struct status>q;
 49 void bfs()
 50 {
 51     while(!q.empty())
 52     {
 53         struct status u = q.front();
 54         q.pop();
 55         if(u.x == c || u.y == c)
 56         {
 57             printf("%d
", u.step);
 58             print_path(u.x, u.y);
 59             return;
 60         }
 61 
 62         if(u.x < a && !vis[a][u.y])
 63         {
 64             q.push((struct status){a, u.y, u.step+1});
 65             vis[a][u.y] = 1;
 66             path[a][u.y] = (struct Path){u.x, u.y, FILL_A};
 67         }
 68 
 69         if(u.y < b && !vis[u.x][b])
 70         {
 71             q.push((struct status){u.x, b, u.step+1});
 72             vis[u.x][b] = 1;
 73             path[u.x][b] = (struct Path){u.x, u.y, FILL_B};
 74         }
 75 
 76         if(u.x > 0 && !vis[0][u.y])
 77         {
 78             q.push((struct status){0, u.y, u.step+1});
 79             vis[0][u.y] = 1;
 80             path[0][u.y] = (struct Path){u.x, u.y, DROP_A};
 81         }
 82 
 83         if(u.y > 0 && !vis[u.x][0])
 84         {
 85             q.push((struct status){u.x, 0, u.step+1});
 86             vis[u.x][0] = 1;
 87             path[u.x][0] = (struct Path){u.x, u.y, DROP_B};
 88         }
 89 
 90         if(u.x > 0 && u.y < b)
 91         {
 92             int tmp = min(u.x, b-u.y);
 93             if(!vis[u.x-tmp][u.y+tmp])
 94             {
 95                 q.push((struct status){u.x-tmp, u.y+tmp, u.step+1});
 96                 vis[u.x-tmp][u.y+tmp] = 1;
 97                 path[u.x-tmp][u.y+tmp] = (struct Path){u.x, u.y, POUR_AB};
 98             }
 99         }
100 
101         if(u.x < a && u.y > 0)
102         {
103             int tmp = min(a-u.x, u.y);
104             if(!vis[u.x+tmp][u.y-tmp])
105             {
106                 q.push((struct status){u.x+tmp, u.y-tmp, u.step+1});
107                 vis[u.x+tmp][u.y-tmp] = 1;
108                 path[u.x+tmp][u.y-tmp] = (struct Path){u.x, u.y, POUR_BA};
109             }
110         }
111     }
112     printf("impossible
");
113 }
114 
115 int main()
116 {
117     scanf("%d %d %d", &a, &b, &c);
118     memset(vis, 0, sizeof(vis));
119     q.push((struct status){0, 0, 0});
120     vis[0][0] = 1;
121     bfs();
122     return 0;
123 }
View Code