• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            A Za, A Za, Fighting...

            堅信:勤能補拙

            PKU 1606 Jugs/PKU 3414 Pots

            問題:
            http://acm.pku.edu.cn/JudgeOnline/problem?id=1606
            http://acm.pku.edu.cn/JudgeOnline/problem?id=3414

            思路:
            典型的BFS
            好玩的就是如何來處理輸出,每個狀態(tài)包含一個指向前一個狀態(tài)的指針

            代碼:
              1 #define QUEUE_LEN 10000
              2 #define MAX_VOL 101
              3 const char ops[][12= {
              4     "FILL(1)",
              5     "FILL(2)",
              6     "DROP(1)",
              7     "DROP(2)",
              8     "POUR(1,2)",
              9     "POUR(2,1)" };
             10 int vola, volb, target;
             11 int head, tail;
             12 int visited[MAX_VOL][MAX_VOL];
             13 struct EACH {
             14     int a, b;
             15     int opnum;
             16     int opidx;
             17     struct EACH *pre;
             18 } queue[QUEUE_LEN];
             19 
             20 #define ADD(na, nb, num, idx) ++tail; \
             21     queue[tail].a = na; \
             22     queue[tail].b = nb; \
             23     queue[tail].opnum = num+1; \
             24     queue[tail].opidx = idx; \
             25     queue[tail].pre = queue+head; \
             26     visited[na][nb] = 1;
             27 
             28 void
             29 output(struct EACH *item)
             30 {
             31     if(item == NULL)
             32         return;
             33     output(item->pre);
             34     if(item->opidx >= 0)
             35         printf("%s\n", ops[item->opidx]);
             36 }
             37 
             38 void
             39 bfs()
             40 {
             41     int cur_a, cur_b, ta, tb, cur_opnum;
             42     queue[tail].a = 0;
             43     queue[tail].b = 0;
             44     queue[tail].opnum = 0;
             45     queue[tail].opidx = -1;
             46     queue[tail].pre = NULL;
             47     visited[0][0= 1;
             48     while(head < tail) {
             49         ++head;
             50         cur_a = queue[head].a;
             51         cur_b = queue[head].b;
             52         cur_opnum = queue[head].opnum;
             53         if(cur_a==target || cur_b==target) {
             54             printf("%d\n", cur_opnum);
             55             output(queue+head);
             56             return;
             57         }
             58         if(!visited[vola][cur_b]) { /* FILL(1) */
             59             ADD(vola, cur_b, cur_opnum, 0);
             60         }
             61         if(!visited[cur_a][volb]) { /* FILL(2) */
             62             ADD(cur_a, volb, cur_opnum, 1);
             63         }
             64         if(!visited[0][cur_b]) { /* DROP(1) */
             65             ADD(0, cur_b, cur_opnum, 2);
             66         }
             67         if(!visited[cur_a][0]) { /* DROP(2) */
             68             ADD(cur_a, 0, cur_opnum, 3);
             69         }
             70         /* POUR(1,2) */
             71         if(cur_a+cur_b > volb) {
             72             ta = cur_a+cur_b-volb;
             73             tb = volb;
             74             if(!visited[ta][tb]) {
             75                 ADD(ta, tb, cur_opnum, 4);
             76             }
             77         } else {
             78             ta = 0;
             79             tb = cur_a + cur_b;
             80             if(!visited[ta][tb]) {
             81                 ADD(ta, tb, cur_opnum, 4);
             82             }
             83         }
             84         /* POUR(2,1) */
             85         if(cur_a+cur_b > vola) {
             86             ta = vola;
             87             tb = cur_a+cur_b-vola;
             88             if(!visited[ta][tb]) {
             89                 ADD(ta, tb, cur_opnum, 5);
             90             }
             91         } else {
             92             ta = cur_a + cur_b;
             93             tb = 0;
             94             if(!visited[ta][tb]) {
             95                 ADD(ta, tb, cur_opnum, 5);
             96             }
             97         }
             98     }
             99     printf("impossible\n");
            100 }

            posted on 2010-07-30 13:45 simplyzhao 閱讀(287) 評論(0)  編輯 收藏 引用 所屬分類: B_搜索

            導(dǎo)航

            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            午夜人妻久久久久久久久| 伊人久久大香线蕉精品不卡| 久久AV无码精品人妻糸列| 精品久久久久久中文字幕大豆网| 亚洲va久久久久| 久久久久夜夜夜精品国产| 久久久久久久91精品免费观看| 中文字幕无码久久人妻| 久久综合给合久久狠狠狠97色69| 国产精品嫩草影院久久| 色综合久久久久无码专区| 2022年国产精品久久久久 | 欧美大香线蕉线伊人久久| 曰曰摸天天摸人人看久久久| 亚洲午夜久久久久久久久电影网| 91麻豆精品国产91久久久久久| 久久经典免费视频| 久久www免费人成看国产片| 国产精品久久久久影院色| 亚洲午夜久久久| 99热精品久久只有精品| 无码精品久久久天天影视 | 77777亚洲午夜久久多喷| 日韩欧美亚洲综合久久影院Ds| 精品久久久久久无码人妻热 | 精品无码久久久久久午夜| 国产精品美女久久福利网站| 亚洲色欲久久久综合网东京热| 精品国产乱码久久久久久1区2区| 久久精品黄AA片一区二区三区| 国产成人久久精品一区二区三区 | 久久久久亚洲av无码专区导航 | 伊人久久久AV老熟妇色| 亚洲va国产va天堂va久久| 久久综合精品国产一区二区三区| 久久久噜噜噜久久| 香蕉久久一区二区不卡无毒影院| 日韩久久久久久中文人妻 | 久久婷婷五月综合色99啪ak| 18岁日韩内射颜射午夜久久成人 | 久久久av波多野一区二区|