• <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>
            隨筆 - 97, 文章 - 22, 評論 - 81, 引用 - 0
            數據加載中……

            Pku 2662 A Walk Through the Forest && HDU 1428 漫步校園 (bfs + dfs)

            首先從終點bfs,保存每一個節點到終點的最短路徑,然后從起點dfs,記憶化,如果滿足題目給定的拓撲序就加上從那個點到終點的路徑數。所謂滿足拓撲序就是題目所給定的taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A,這句話仔細讀上幾十遍就能明白題目意圖了。

            漫步校園
            代碼:

            #include <iostream>
            #include 
            <queue>
            using namespace std;

            int dir[4][2= {{01}{0-1}{10}{-10}};
            struct point {
                
            int x;
                
            int y;
                
            int time;

                
            bool friend operator < (point a, point b) {
                    
            return a.time > b.time;
                }


            }
            temp, tt;

            priority_queue 
            < point > q;
            int hash[51][51], map[51][51];
            __int64 dp[
            51][51];
            int n;

            __int64 dfs(
            int x, int y) {
                
                
            int i;
                
            int tx, ty;
                __int64 sum 
            = 0;

                
            if(x == n && y == n)
                    
            return 1;

                
            for(i = 0; i < 4; i++{
                    tx 
            = x + dir[i][0];
                    ty 
            = y + dir[i][1];
                    
            if(tx < 1 || ty < 1 || tx > n || ty > n)
                        
            continue;
                    
            if(hash[x][y] > hash[tx][ty]) {
                        
            if(dp[tx][ty] == -1{
                            dp[tx][ty] 
            = dfs(tx, ty);
                        }

                        sum 
            += dp[tx][ty];
                    }

                }


                
            return sum;
            }

            int main() {
                
            int i, j;
                
            while(scanf("%d"&n) != EOF) {

                    
            for(i = 1; i <= n; i++{
                        
            for(j = 1; j <= n; j++{
                            scanf(
            "%d"&map[i][j]);
                        }

                    }

                    temp.x 
            = n;
                    temp.y 
            = n;
                    temp.time 
            = map[n][n];
                    memset(hash, 
            -1sizeof(hash));
                    hash[n][n] 
            = map[n][n];
                    
            while(!q.empty())
                        q.pop();

                    q.push( temp );

                    
            while(!q.empty()) {
                        temp 
            = q.top();
                        q.pop();
                        
            for(i = 0; i < 4; i++{
                            tt.x 
            = temp.x + dir[i][0];
                            tt.y 
            = temp.y + dir[i][1];
                            
            if(tt.x < 1 || tt.y < 1 || tt.x > n || tt.y > n)
                                
            continue;
                            tt.time 
            = temp.time + map[tt.x][tt.y];
                            
                            
            if(hash[ tt.x ][ tt.y ] == -1 || tt.time < hash[ tt.x ][ tt.y ]) {
                                hash[ tt.x ][ tt.y ] 
            = tt.time;
                                q.push( tt );
                            }

                        }

                    }


                    memset(dp, 
            -1sizeof(dp));

                    dp[
            1][1= dfs(11);
                    printf(
            "%I64d\n", dp[1][1]);
                }

                
            return 0;
            }

            posted on 2009-03-09 19:12 英雄哪里出來 閱讀(718) 評論(2)  編輯 收藏 引用 所屬分類: ACM

            評論

            # re: Pku 2662 A Walk Through the Forest && HDU 1428 漫步校園 (bfs + dfs)  回復  更多評論   

            taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A

            這句話就是說有拓撲序了,啊…… 太強了,Orz!!
            我都不知道是什么意思!
            2009-12-03 10:28 | huangzhifei

            # re: Pku 2662 A Walk Through the Forest && HDU 1428 漫步校園 (bfs + dfs)  回復  更多評論   

            我就是想過不用DFS,用BFS去遍歷所獲得的耗時表,為什么不行呢?
            詳細的情況:http://acm.hdu.edu.cn/forum/read.php?tid=17192
            希望你能幫我看看,感激不盡~~
            2010-07-23 11:05 | Geek.tan
            国产免费福利体检区久久| 国产福利电影一区二区三区,免费久久久久久久精 | 久久综合给久久狠狠97色| 中文字幕乱码久久午夜| 狠狠狠色丁香婷婷综合久久五月 | 麻豆成人久久精品二区三区免费| 77777亚洲午夜久久多喷| 久久久国产乱子伦精品作者| 99热热久久这里只有精品68| 亚洲国产精品综合久久一线| 久久久久久久亚洲Av无码| 久久精品国产亚洲5555| 99热成人精品热久久669| 久久久久亚洲AV无码专区桃色| 亚洲中文久久精品无码ww16| 99久久国产免费福利| 一本色道久久88—综合亚洲精品| 日韩精品国产自在久久现线拍| 97久久国产综合精品女不卡| 久久精品国产国产精品四凭| 久久国产精品无码HDAV| 久久夜色精品国产噜噜亚洲a| 久久精品a亚洲国产v高清不卡| 中文精品久久久久国产网址| 亚洲国产精品久久电影欧美| 久久久中文字幕日本| 国产精品久久久久久久久久免费| 久久亚洲春色中文字幕久久久| 2021国产精品午夜久久| 污污内射久久一区二区欧美日韩 | 99re久久精品国产首页2020| 亚洲中文字幕无码久久综合网| 一本久道久久综合狠狠爱| a高清免费毛片久久| 欧美精品丝袜久久久中文字幕| 99精品伊人久久久大香线蕉| 2021精品国产综合久久| 亚洲欧美伊人久久综合一区二区| 久久香综合精品久久伊人| 久久精品国产99国产精品导航| 国产精品美女久久福利网站|