• <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 1691 Painting A Board

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

            思路:
            首先要解決的問題是如何合理地表示整個Board?
            這題還是在青島洲際無聊的時候用手機看到的,當時想到用一顆樹的父子節點來表示各個矩形之間的上下關系
            其實,這是一個有向圖,而表示的方法則可以很簡單地使用二維數組(因為矩形的個數比較少)進行標記即可
            另一個巧妙之處是記錄每個節點的入度,當入度為零時表示可以Painting
            在用有向圖進行表示之后,剩下的就是搜索了(太菜,參考人家的)

            代碼:
             1 int
             2 solve(int last_color, int count)
             3 {
             4     int i, j, rt;
             5     int ans = 1000000;
             6     for(i=0; i<n; i++) {
             7         if(!visited[i] && degree[i]==0) {
             8             visited[i] = 1;
             9             if(recs[i].color != last_color)
            10                 ++count;
            11             for(j=0; j<n; j++)
            12                 if(graph[i][j])
            13                     --degree[j];
            14             rt = solve(recs[i].color, count);
            15             ans = rt<ans ? rt : ans;
            16             visited[i] = 0;
            17             if(recs[i].color != last_color)
            18                 --count;
            19             for(j=0; j<n; j++)
            20                 if(graph[i][j])
            21                     ++degree[j];
            22         }
            23     }
            24     if(ans == 1000000)
            25         ans = count;
            26     return ans;
            27 }

             1 void
             2 build_graph()
             3 {
             4     int i, j;
             5     for(i=0; i<n; i++
             6         for(j=0; j<n; j++
             7             if(i!=&& is_immdt_above(recs+i, recs+j)) {
             8                 graph[i][j] = 1;
             9                 ++degree[j];
            10             }
            11 }

            1 /* if rec1 is immediate above rec2, return 1 */
            2 int
            3 is_immdt_above(struct Rec *rec1, struct Rec *rec2)
            4 {
            5     if(rec1->lwrgt_x==rec2->uplft_x && !(rec1->lwrgt_y<=rec2->uplft_y || rec1->uplft_y>=rec2->lwrgt_y))
            6         return 1;
            7     return 0;
            8 }

            posted on 2010-07-24 09:33 simplyzhao 閱讀(185) 評論(0)  編輯 收藏 引用 所屬分類: B_搜索

            導航

            <2011年10月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲国产欧美国产综合久久| 久久久久亚洲AV成人网| 精品乱码久久久久久久| 国产亚洲精午夜久久久久久| 一日本道伊人久久综合影| 久久天天躁狠狠躁夜夜躁2O2O| 久久国产精品-国产精品| 久久夜色撩人精品国产小说| 久久亚洲欧美国产精品| 四虎国产精品成人免费久久| 久久99精品国产99久久6男男| 久久男人中文字幕资源站| 97久久久精品综合88久久| 亚洲?V乱码久久精品蜜桃| 久久精品国产精品青草app| 精品久久久无码人妻中文字幕| 久久精品亚洲男人的天堂| 国产精品久久久福利| 亚洲午夜久久久久久久久电影网| 久久久久久久久久久免费精品| 久久国产精品99精品国产987| 久久大香香蕉国产| 久久香蕉超碰97国产精品| 99久久精品国产一区二区| 久久人做人爽一区二区三区| 久久久WWW免费人成精品| 精品综合久久久久久88小说| 麻豆精品久久精品色综合| 99久久久精品| 国产精品毛片久久久久久久| 99精品久久精品一区二区| 久久精品国产秦先生| 久久99精品久久久久久久不卡 | 亚洲熟妇无码另类久久久| 一日本道伊人久久综合影| 精品伊人久久大线蕉色首页| 久久久黄色大片| 精品久久久无码人妻中文字幕豆芽| 一本久久知道综合久久| 久久永久免费人妻精品下载| 东京热TOKYO综合久久精品|