• <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>

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數(shù)據(jù)加載中……

            POJ 3170 Knights of Ni 寬搜

            思路:
            一次寬搜就可以解決了。
            每個搜索節(jié)點需要保存一個 stat 值:如果攜帶了 shrubbery 則 stat = 1。否則為 0。
            地圖上的每個點也保存一個 stat 值:如果沒經(jīng)過則stat = 0;如果空著手經(jīng)過則stat = 1;如果帶著shrubbery經(jīng)過則stat = 2。
            判重的時候,如果地圖的 stat 值大于搜索節(jié)點的 stat 值就可以忽略了。

            代碼 266ms:
            #include <stdio.h>

            #define SIZE 1024

            struct map_node {
                
            int type, stat;
            }
            ;
            struct map_node map[SIZE][SIZE];

            struct queue_node {
                
            int step, x, y, stat;
            }
            ;
            struct queue_node queue[SIZE * SIZE * 2];

            int W, H, qh, qt;

            __inline 
            int push(int y, int x, int stat, int step)
            {
                
            if (y < 0 || y >= H || x < 0 || x >= W)
                    
            return 0;
                
            if (map[y][x].type == 1)
                    
            return 0;
                
            if (map[y][x].type == 3)
                    
            return stat;
                
            if (map[y][x].type == 4)
                    stat 
            = 1;
                
            if (map[y][x].stat > stat)
                    
            return 0;

                map[y][x].stat
            ++;
                queue[qt].stat 
            = stat;
                queue[qt].y 
            = y;
                queue[qt].x 
            = x;
                queue[qt].step 
            = step;
                qt
            ++;

                
            return 0;
            }


            int main()
            {
                
            int i, j;
                
            struct queue_node *t;

                freopen(
            "e:\\test\\in.txt""r", stdin);

                t 
            = &queue[qt++];
                scanf(
            "%d%d"&W, &H);
                
            for (i = 0; i < H; i++{
                    
            for (j = 0; j < W; j++{
                        scanf(
            "%d"&map[i][j].type);
                        
            if (map[i][j].type == 2{
                            t
            ->= i;
                            t
            ->= j;
                        }

                    }

                }


                
            while (qh != qt) {
                    t 
            = &queue[qh++];
                    
            if (push(t->- 1, t->x, t->stat, t->step + 1||
                        push(t
            ->+ 1, t->x, t->stat, t->step + 1||
                        push(t
            ->y, t->- 1, t->stat, t->step + 1||
                        push(t
            ->y, t->+ 1, t->stat, t->step + 1)
                        )
                        
            break;
                }

                printf(
            "%d\n", t->step + 1);

                
            return 0;
            }

            posted on 2010-03-31 13:03 糯米 閱讀(319) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            色婷婷综合久久久久中文一区二区| 青草国产精品久久久久久| 亚洲精品蜜桃久久久久久| 国产一区二区三区久久| 久久免费视频6| 成人免费网站久久久| 色悠久久久久久久综合网| 久久国产免费观看精品| 老司机午夜网站国内精品久久久久久久久| 蜜臀久久99精品久久久久久| 亚洲AV日韩AV天堂久久| 91精品国产高清久久久久久91| 麻豆亚洲AV永久无码精品久久| 91久久香蕉国产熟女线看| 久久久噜噜噜久久中文字幕色伊伊| 久久97久久97精品免视看| 狠狠色丁香久久综合婷婷| 久久噜噜久久久精品66| 国产精品视频久久| 成人综合久久精品色婷婷| 亚洲国产成人久久综合碰| 久久久久亚洲精品男人的天堂| 漂亮人妻被黑人久久精品| 一本大道久久东京热无码AV| 国产L精品国产亚洲区久久| 99久久夜色精品国产网站| 亚洲中文久久精品无码ww16| 久久久久久亚洲精品成人| 久久久久人妻一区精品性色av| 伊色综合久久之综合久久| 狠狠色狠狠色综合久久| 久久中文字幕视频、最近更新 | 久久久久亚洲AV成人网人人网站 | 亚洲国产小视频精品久久久三级| 国产精品久久久久jk制服| 亚洲狠狠久久综合一区77777 | 综合久久一区二区三区 | 中文字幕久久精品 | 精品国产VA久久久久久久冰| 欧美牲交A欧牲交aⅴ久久| 伊人久久精品无码av一区|