• <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 2312 Battle City (Cont.)

            問題:
            http://poj.org/problem?id=2312

            思路:
            http://www.shnenglu.com/Joe/archive/2010/10/23/130973.html中,參考網上代碼采用了一種"新"的BFS方法來解題,該方法的一個缺點在于每個點可能多次進入隊列,這也直接導致了單個點的多次擴展

            其實,這題可以采用原始的BFS方法來做,只是不能再用普通的隊列,而需要使用優先級隊列
            通過這題,使我對于寬度優先搜索有了新的認識
            普通的BFS之所以能夠找到最小的步數,關鍵在于它是單步擴展的,也就是說它首先羅列出所有在一步之內可以到達的點,然后再羅列所有在兩步之內可以到達的點,類似于"1-1-1...-2-2-2...-3-3-3..."的方式
            這題在擴展的時候并非都是一步,所以普通的BFS并不能找出正確的解,例如:
            Y B
            E T
            假如我們以右、下、左、上的順序進行擴展,那么我們將得出結果是3,而事實上只需要2

            優先級隊列之所以能夠找出正確解,是因為它保證我們始終從最小步數的點開始擴展

            代碼(C++)
             1 /* 0MS */
             2 #include<iostream>
             3 #include<cstdio>
             4 #include<cstring>
             5 #include<queue> /* priority queue */
             6 using namespace std;
             7 
             8 #define MAX_LEN 301
             9 #define is_valid(x, y) ((x)>=0 && (x)<M && (y)>=0 && (y)<N)
            10 char map[MAX_LEN][MAX_LEN];
            11 const int dx[] = {00-11};
            12 const int dy[] = {-1100};
            13 int M, N;
            14 int you_x, you_y, target_x, target_y;
            15 int visited[MAX_LEN][MAX_LEN];
            16 struct Node {
            17     int x, y;
            18     int steps;
            19     bool operator<(const Node &item) const {
            20         return steps > item.steps;
            21     }
            22 }cur, next;
            23 priority_queue<Node> states;
            24 
            25 int
            26 bfs()
            27 {
            28     int i;
            29     memset(visited, 0sizeof(visited));
            30     while(!states.empty()) /* empty the queue */
            31         states.pop();
            32     next.x = you_x;
            33     next.y = you_y;
            34     next.steps = 0;
            35     visited[you_x][you_y] = 1;
            36     states.push(next);
            37     while(!states.empty()) {
            38         cur = states.top();
            39         states.pop();
            40         if(cur.x==target_x && cur.y==target_y)
            41             return cur.steps;
            42         for(i=0; i<4; i++) {
            43             next.x = cur.x + dx[i];
            44             next.y = cur.y + dy[i];
            45             if(!visited[next.x][next.y]) {
            46                 visited[next.x][next.y] = 1;
            47                 if(map[next.x][next.y]=='E' || map[next.x][next.y]=='T') {
            48                     next.steps = cur.steps+1;
            49                     states.push(next);
            50                 } else if(map[next.x][next.y]=='B') {
            51                     next.steps = cur.steps+2;
            52                     states.push(next);
            53                 }
            54             }
            55         }
            56     }
            57     return -1;
            58 }
            59 
            60 int
            61 main(int argc, char **argv)
            62 {
            63     int i, j;
            64     while(scanf("%d %d"&M, &N)!=EOF && M && N) {
            65         for(i=0; i<M; i++) {
            66             scanf("%s", map[i]);
            67             for(j=0; j<N; j++) {
            68                 if(map[i][j] == 'Y') {
            69                     you_x = i;
            70                     you_y = j;
            71                 } else if(map[i][j] == 'T') {
            72                     target_x = i; 
            73                     target_y = j;
            74                 }
            75             }
            76         }
            77         printf("%d\n", bfs());
            78     }
            79 }

            posted on 2010-10-23 20:10 simplyzhao 閱讀(193) 評論(0)  編輯 收藏 引用 所屬分類: B_搜索

            導航

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

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            影音先锋女人AV鲁色资源网久久| 久久婷婷人人澡人人| 99久久精品国产一区二区| 久久久婷婷五月亚洲97号色| 国产精品久久久久久福利漫画| 精品无码人妻久久久久久| 亚洲精品视频久久久| 久久精品aⅴ无码中文字字幕不卡| 日韩精品久久久久久久电影蜜臀| 国产999精品久久久久久| 国产精品成人久久久| 久久福利青草精品资源站免费| 欧美成a人片免费看久久| 久久精品蜜芽亚洲国产AV| 久久精品国产亚洲AV不卡| 久久精品www人人爽人人| 伊人 久久 精品| 色综合久久天天综合| 天天躁日日躁狠狠久久| 久久久久亚洲精品中文字幕| 久久精品国产69国产精品亚洲| 蜜桃麻豆WWW久久囤产精品| 精品国产91久久久久久久a| 99久久99久久| A狠狠久久蜜臀婷色中文网| 伊人久久久AV老熟妇色| 偷偷做久久久久网站| 久久无码人妻精品一区二区三区| 久久久久夜夜夜精品国产| 国产91久久精品一区二区| 人妻无码中文久久久久专区 | 久久w5ww成w人免费| 囯产极品美女高潮无套久久久| 久久久久亚洲AV成人网| 成人精品一区二区久久| 国产91久久综合| 久久免费观看视频| 久久综合久久综合亚洲| 伊人久久大香线蕉亚洲| 无码超乳爆乳中文字幕久久| 久久国产精品无码HDAV|