• <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 英雄哪里出來 閱讀(469) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            2021国产精品久久精品| 亚洲色欲久久久综合网| 蜜桃麻豆www久久| 综合人妻久久一区二区精品| 亚洲欧美成人综合久久久| 久久不见久久见免费影院www日本| 蜜桃麻豆WWW久久囤产精品| 少妇久久久久久久久久| 91精品国产高清久久久久久国产嫩草| 久久久久人妻一区二区三区 | 亚洲国产精品无码久久青草| 久久久久亚洲av无码专区喷水 | 热re99久久6国产精品免费| 久久精品国产欧美日韩| 久久久久四虎国产精品| 久久亚洲国产成人影院| 亚洲欧洲精品成人久久奇米网| 久久久无码精品亚洲日韩蜜臀浪潮| 精品久久久久中文字| 久久亚洲私人国产精品| 久久综合久久综合亚洲| 色综合色天天久久婷婷基地| 久久国产高潮流白浆免费观看| 亚洲精品综合久久| 久久久久一级精品亚洲国产成人综合AV区 | 久久久久一本毛久久久| 国产亚洲精午夜久久久久久 | A级毛片无码久久精品免费| 久久黄视频| 久久久久国产精品嫩草影院| 亚洲精品国产成人99久久| 国产精品对白刺激久久久| 亚洲精品国产成人99久久| 奇米影视7777久久精品| 久久99精品久久久大学生| 久久无码中文字幕东京热| 国内精品久久国产| 色88久久久久高潮综合影院| 无码人妻久久一区二区三区 | 亚洲级αV无码毛片久久精品| 精品国产日韩久久亚洲|