BFS POJ 3414 Pots-白红宇

BFS POJ 3414 Pots

阅读量：6852 次

发布时间：2019-06-26

本文共 2736 字，大约阅读时间需要 9 分钟。

1 /*  2     BFS：六种情况讨论一下，BFS轻松解决  3     起初我看有人用DFS，我写了一遍，TLE。。还是用BFS，结果特判时出错，逗了好长时间  4     看别人的代码简直是受罪，还好自己终于发现自己代码的小错误：)  5 */  6 /************************************************  7 Author        :Running_Time  8 Created Time  :2015-8-3 14:17:24  9 File Name     :POJ_3414_BFS.cpp 10 **************************************************/ 11  12 #include 
     
       13 #include 
      
        14 #include 
       
         15 #include 
        
          16 #include 
         
           17 #include 
          
            18 #include 
           
             19 #include 
            
              20 #include 
             
               21 #include 
              
                22 #include 
               
                 23 #include 
                
                  24 #include 
                  25 #include 
                  
                    26 #include 
                   
                     27 #include 
                    
                      28 #include 
                     
                       29 using namespace std; 30 31 #define lson l, mid, rt << 1 32 #define rson mid + 1, r, rt << 1 | 1 33 typedef long long ll; 34 const int MAXN = 1e4 + 10; 35 const int INF = 0x3f3f3f3f; 36 const int MOD = 1e9 + 7; 37 struct Point { 38 int a, b, step; 39 int op[MAXN]; 40 }; 41 bool vis[110][110]; 42 int A, B, C; 43 int ans; 44 45 void BFS(void) { 46 memset (vis, false, sizeof (vis)); 47 queue
                      
                        Q; Q.push ((Point) { 0, 0, 0}); 48 while (!Q.empty ()) { 49 Point p = Q.front (); Q.pop (); 50 if (p.a == C || p.b == C) { 51 printf ("%d\n", p.step); 52 for (int i=1; i<=p.step; ++i) { 53 if (p.op[i] == 1) puts ("FILL(1)"); 54 else if (p.op[i] == 2) puts ("FILL(2)"); 55 else if (p.op[i] == 3) puts ("DROP(1)"); 56 else if (p.op[i] == 4) puts ("DROP(2)"); 57 else if (p.op[i] == 5) puts ("POUR(1,2)"); 58 else if (p.op[i] == 6) puts ("POUR(2,1)"); 59 } 60 return ; 61 } 62 Point tmp; 63 if (p.a < A && !vis[A][p.b]) { 64 vis[A][p.b] = true; 65 tmp = p; tmp.a = A; tmp.op[++tmp.step] = 1; //FILL1 66 Q.push (tmp); 67 } 68 if (p.b < B && !vis[p.a][B]) { 69 vis[p.a][B] = true; 70 tmp = p; tmp.b = B; tmp.op[++tmp.step] = 2; //FILL2 71 Q.push (tmp); 72 } 73 if (p.a > 0 && !vis[0][p.b]) { 74 vis[0][p.b] = true; 75 tmp = p; tmp.a = 0; tmp.op[++tmp.step] = 3; //DROP1 76 Q.push (tmp); 77 } 78 if (p.b > 0 && !vis[p.a][0]) { 79 vis[p.a][0] = true; 80 tmp = p; tmp.b = 0; tmp.op[++tmp.step] = 4; //DROP2 81 Q.push (tmp); 82 } 83 if (p.a > 0 && p.b < B) { 84 int t = min (p.a, B - p.b); 85 if (!vis[p.a-t][p.b+t]) { 86 vis[p.a-t][p.b+t] = true; //POUR1->2 87 tmp = p; tmp.a -= t; tmp.b += t; tmp.op[++tmp.step] = 5; 88 Q.push (tmp); 89 } 90 } 91 if (p.b > 0 && p.a < A) { 92 int t = min (p.b, A - p.a); 93 if (!vis[p.a+t][p.b-t]) { 94 vis[p.a+t][p.b-t] = true; //POUR2->1 95 tmp = p; tmp.a += t; tmp.b -= t; tmp.op[++tmp.step] = 6; 96 Q.push (tmp); 97 } 98 } 99 }100 101 puts ("impossible");102 }103 104 int main(void) { //POJ 3414 Pots105 while (scanf ("%d%d%d", &A, &B, &C) == 3) {106 BFS ();107 }108 109 return 0;110 }