• <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 糯米 閱讀(321) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            91精品国产综合久久精品| 久久这里只精品99re66| 97久久超碰国产精品旧版| 日本免费一区二区久久人人澡| 88久久精品无码一区二区毛片| 日韩欧美亚洲综合久久影院Ds | 久久国产午夜精品一区二区三区| 久久久久国产一区二区三区| 一本一本久久A久久综合精品| 久久精品国产亚洲AV高清热| 久久噜噜久久久精品66| 一本久久知道综合久久| 久久久久人妻一区精品| 99久久er这里只有精品18| 人妻丰满?V无码久久不卡| 久久精品草草草| 日日噜噜夜夜狠狠久久丁香五月| 久久国产午夜精品一区二区三区| 久久99精品久久久久婷婷| 久久久久久久波多野结衣高潮| 亚洲国产精品婷婷久久| 久久亚洲AV成人无码电影| 亚洲国产成人久久综合野外| 亚洲午夜久久影院| 久久亚洲高清观看| 99久久精品毛片免费播放| 久久久久久国产精品美女| 国内精品久久久久影院日本| 一级A毛片免费观看久久精品| 色综合久久88色综合天天| 999久久久免费精品国产| 亚洲色大成网站www久久九| 午夜精品久久久久久| 久久久亚洲精品蜜桃臀| 久久综合精品国产一区二区三区| 国产精品日韩深夜福利久久| 久久精品国产91久久综合麻豆自制 | 日韩人妻无码精品久久免费一| 婷婷久久综合九色综合九七| 久久亚洲电影| 久久婷婷五月综合成人D啪 |