POJ 3414 Pots bfs印刷方式

テーマ:http://poj.org/problem?id=3414
とても面白い問題です.肝心なのはまた16 ms 1 Aで、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