• <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 1383 Labyrinth && Zju 3172 Extend 7-day Vacation (最長路)

            求任意圖的最長路。

            其實思路很簡單,兩次bfs即可。
            首先在圖中任意選擇一個點,對它進行bfs擴展,找到距該點最遠的點,然后再一次bfs尋找最遠點,此時找到的最遠距離就是最長路的大小。

            Pku 1383 Labyrinth 代碼:

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

            int dir[4][2= {{01}{0-1}{10}{-10}};

            struct point {
                
            int x;
                
            int y;
                
            int step;
            }
            temp, tt;

            int n, m;
            point q[
            1500000];
            int hash[1002][1002];
            char map[1002][1002];
            int rear, front;

            void bfs(point temp) {
                
            int i;

                memset(hash, 
            0sizeof(hash));
                rear 
            = front = 0;

                hash[ temp.x ][ temp.y ] 
            = 0;
                q[ rear 
            ++ ] = temp;
                
            while(front < rear) {
                    temp 
            = q[ front++ ];

                    
            for(i = 0; i < 4; i++{
                        tt.x 
            = temp.x + dir[i][0];
                        tt.y 
            = temp.y + dir[i][1];
                        tt.step 
            = temp.step + 1;
                        
            if(tt.x < 0 || tt.y < 0 || tt.x >= n || tt.y >= m)
                            
            continue;
                        
            if(map[tt.x][tt.y] == '.' && !hash[ tt.x ][ tt.y ]) {
                            hash[ tt.x ][ tt.y ] 
            = tt.step;
                            q[ rear 
            ++ ] = tt;
                        }

                    }

                }

            }


            int main() {

                
            int t;
                
            int i, j;
                scanf(
            "%d"&t);

                
            while(t--{
                    scanf(
            "%d %d"&m, &n);

                    
            for(i = 0; i < n; i++{
                        scanf(
            "%s", map[i]);
                    }


                    
            int flag = 0;
                    
            for(i = 0; i < n; i++{
                        
            for(j = 0; j < m; j++{
                            
            if(map[i][j] == '.'{
                                temp.x 
            = i;
                                temp.y 
            = j;
                                temp.step 
            = 0;
                                flag 
            = 1;
                                
            break;
                            }

                        }

                        
            if(flag)
                            
            break;
                    }


                    bfs(temp);
                    temp.step 
            = 0;

                    
            for(i = 0; i < n; i++{
                        
            for(j = 0; j < m; j++{
                            
            if(hash[i][j] > temp.step) {
                                temp.step 
            = hash[i][j];
                                temp.x 
            = i;
                                temp.y 
            = j;
                            }

                        }

                    }



                    temp.step 
            = 0;
                    bfs(temp);
                    temp.step 
            = 0;
                    
            for(i = 0; i < n; i++{
                        
            for(j = 0; j < m; j++{
                            
            if(hash[i][j] > temp.step) {
                                temp.step 
            = hash[i][j];
                                temp.x 
            = i;
                                temp.y 
            = j;
                            }

                        }

                    }

                    printf(
            "Maximum rope length is %d.\n", temp.step);


                }

            }


            Zju 3172 Extend 7-day Vacation 代碼:
            #include <iostream>
            #include 
            <vector>
            #include 
            <queue>
            using namespace std;

            struct point {
                
            int now;
                
            int step;
            }
            temp, tt;

            vector 
            < int > vec[1001];
            int hash[1001];
            int n, m, x, y;
            int i, j;
            bool exsit[1001];
            queue 
            < point > q;

            void bfs(point temp) {

                
            int i;
                
            while(!q.empty())
                    q.pop();
                q.push( temp );
                hash[ temp.now ] 
            = 0;
                memset(hash, 
            -1sizeof(hash));

                
            while(!q.empty()) {

                    temp 
            = q.front();
                    q.pop();
                    
            int size = vec[ temp.now ].size();

                    
            for(i = 0; i < size; i++{
                        
            if(hash[ vec[temp.now][i] ] == -1{
                            
                            tt.now 
            = vec[temp.now][i];
                            tt.step 
            = temp.step + 1;

                            hash[ vec[temp.now][i] ] 
            = tt.step;
                            q.push( tt );
                        }

                    }

                }

            }

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

                    memset(exsit, 
            0sizeof(exsit));

                    
            for(i = 0; i < n; i++)
                        vec[i].clear();
                    
                    
            while(m --{
                        scanf(
            "%d %d"&x, &y);
                        vec[x].push_back( y );
                        vec[y].push_back( x );
                        exsit[x] 
            = exsit[y] = 1;
                    }


                    
            for(i = 0; i < n; i++{
                        
            if(exsit[i] == 1)
                            
            break;
                    }

                    temp.now 
            = i;
                    temp.step 
            = 0;
                    bfs(temp);
                    
            for(i = 0; i < n; i++{
                        
            if(hash[i] > temp.step) {
                            temp.step 
            = hash[i];
                            temp.now 
            = i;
                        }

                    }

                    temp.step 
            = 0;

                    bfs(temp);
                

                    
            for(i = 0; i < n; i++{
                        
            if(hash[i] > temp.step) {
                            temp.step 
            = hash[i];
                            temp.now 
            = i;
                        }

                    }

                    
            if(temp.step < 7)
                        printf(
            "Impossible\n");
                    
            else
                        printf(
            "%d\n", temp.step + 1);
                }

                
            return 0;
            }

            posted on 2009-03-10 23:48 英雄哪里出來 閱讀(468) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            久久精品国产亚洲AV电影| 精品乱码久久久久久夜夜嗨| 亚洲欧美另类日本久久国产真实乱对白| 办公室久久精品| 欧美日韩精品久久久久| 97精品依人久久久大香线蕉97| 久久久久久久人妻无码中文字幕爆| 久久中文娱乐网| 中文字幕精品久久| 久久免费高清视频| 合区精品久久久中文字幕一区 | 久久久精品人妻无码专区不卡| 久久久国产亚洲精品| 精品国际久久久久999波多野| 久久国产V一级毛多内射| 精品久久久中文字幕人妻| 久久久精品一区二区三区| 97久久国产露脸精品国产| 久久国产精品久久| 久久久久久久精品成人热色戒| 久久精品国产一区| 亚洲国产精品无码久久久秋霞2| 精品久久久久久国产免费了| 精品久久久久香蕉网| 久久久久se色偷偷亚洲精品av| 国产精品亚洲综合专区片高清久久久| 人妻精品久久无码专区精东影业 | 久久久久女人精品毛片| 色妞色综合久久夜夜| 欧美色综合久久久久久| 国产免费久久久久久无码| 久久精品国产99国产电影网| 久久婷婷国产剧情内射白浆| 色播久久人人爽人人爽人人片aV| 色综合久久久久网| 久久综合欧美成人| 国产精品99久久精品爆乳| 2020最新久久久视精品爱| 91久久成人免费| 国产精品狼人久久久久影院| 国产精品欧美久久久久天天影视|