• <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
            數(shù)據(jù)加載中……

            Pku 3346 Treasure of the Chimp Island (Bfs)

            去年做杭州網(wǎng)賽的時候遇到的題目,當時一點思路都沒有,過后一直沒去做,今天看了一下,發(fā)現(xiàn)其實和hdu的1044很像,可以先縮圖,然后bfs,我用了兩次bfs實現(xiàn)。具體思路是對于每一個非墻非走廊的點進行bfs,擴展和它相鄰的非墻非走廊的點,保存到鄰接表中,然后對于所有邊界上是gate的點進行bfs,用優(yōu)先隊列實現(xiàn),狀態(tài)為三維,即坐標+內(nèi)力,其實可以將每個點離散化到一個數(shù)字,以減少內(nèi)存開銷來換取時間。

            代碼如下:
            #include <iostream>
            #include 
            <vector>
            #include 
            <queue>
            using namespace std;

            int dir[4][2= {{01}{0-1}{10}{-10}};
            struct point {
                
            int x;
                
            int y;
                
            int num;
                
            int step;
                
            bool friend operator < (point a, point b) {
                    
            return a.step > b.step;
                }

            }
            temp, tt;

            char map[110][110];
            vector 
            < point > vec[101][101];
            int n, m;
            int hash[101][101];
            priority_queue 
            < point > q;
            __int8 visit[
            100][100][27];
            int ans;

            //縮圖
            void bfs(int x, int y) {

                
            int i;
                temp.x 
            = x;
                temp.y 
            = y;
                memset(hash, 
            0sizeof(hash));
                
            while(!q.empty() )
                    q.pop();

                q.push( temp );
                hash[ temp.x ][ temp.y ] 
            = 1;

                
            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 < 0 || tt.y < 0 || tt.x == n || tt.y == m)
                            
            continue;
                        
            if(map[tt.x][tt.y] == '*'
                            
            continue;
                        
            if(map[tt.x][tt.y] >= 'A' && map[tt.x][tt.y] <= 'Z')
                            
            continue;
                        
            if(map[tt.x][tt.y] == '#')
                            
            continue;
                        
            if(hash[ tt.x ][ tt.y ])
                            
            continue;

                        
            if(!hash[ tt.x ][ tt.y ] ) {
                            hash[ tt.x ][ tt.y ] 
            = 1;

                            
            if(map[tt.x][tt.y] == '.')
                                q.push( tt );
                            
            else {
                                vec[x][y].push_back( tt );
                            }

                        }

                    }

                }

            }


            //求最短距離
            int BFS(int x, int y, int num) {

                
            int i;
                temp.step 
            = 0;
                temp.x 
            = x;
                temp.y 
            = y;
                temp.num 
            = num;

                
            while(!q.empty())
                    q.pop();

                memset(visit, 
            -1sizeof(visit));
                q.push( temp );

                visit[ temp.x ][ temp.y ][ temp.num ] 
            = 0;

                
            while!q.empty() ) {
                    temp 
            = q.top();
                    q.pop();

                    
            if(temp.step > ans && ans != -1)
                        
            return -1;

                    
            if( map[ temp.x ][ temp.y ] == '$')
                        
            return temp.step;

                    
            int size = vec[ temp.x ][ temp.y ].size();

                    
            for(i = 0; i < size; i++{
                        point rt 
            = vec[ temp.x ][ temp.y ][ i ];

                        
            if(map[rt.x][rt.y] == '$'{
                            tt.num 
            = temp.num;
                            tt.step 
            = temp.step;

                            tt.x 
            = rt.x;
                            tt.y 
            = rt.y;
                            
            if(tt.step < visit[ tt.x ][ tt.y ][ tt.num ]
                                
            || visit[ tt.x ][ tt.y ][ tt.num ] == -1{
                                visit[ tt.x ][ tt.y ][ tt.num ] 
            = tt.step;
                                q.push( tt );
                            }

                            
            continue;
                        }


                        
            if(temp.num) {
                            tt.num 
            = temp.num - 1;
                            tt.step 
            = temp.step;
                            tt.x 
            = rt.x;
                            tt.y 
            = rt.y;
                            
            if(tt.step < visit[ tt.x ][ tt.y ][ tt.num ]
                                
            || visit[ tt.x ][ tt.y ][ tt.num ] == -1{
                                visit[ tt.x ][ tt.y ][ tt.num ] 
            = tt.step;
                                q.push( tt );
                            }

                        }


                        tt.num 
            = temp.num;
                        tt.step 
            = temp.step + map[rt.x][rt.y] - '0';
                        tt.x 
            = rt.x;
                        tt.y 
            = rt.y;

                        
            if(tt.step < visit[ tt.x ][ tt.y ][ tt.num ]
                            
            || visit[ tt.x ][ tt.y ][ tt.num ] == -1{
                            visit[ tt.x ][ tt.y ][ tt.num ] 
            = tt.step;
                            q.push( tt );
                        }

                    }

                }


                
            return -1;
            }


            int main() {

                
            int i, j;
                
            while(1{

                    
            while(gets(map[0])) {
                        
            if( strcmp(map[0], "") )
                            
            break;
                    }
                    
                    m 
            = strlen( map[0] );

                    
            if(strcmp(map[0], "--"== 0)
                        
            break;

                    n 
            = 1;
                    
            while(gets(map[n])) {
                        
            if(strcmp( map[n], "" ) == 0)
                            
            break;
                        
            else
                            n 
            ++;
                    }


                    
            for(i = 0; i < n; i++{
                        
            for(j = 0;j < m; j++)
                            vec[i][j].clear();
                    }


                    
            for(i = 0; i < n; i++{

                        
            for(j = 0; j < m; j++{

                            
            if(map[i][j] >= '1' && map[i][j] <= '9'{
                                bfs(i, j);
                            }


                            
            if(map[i][j] >= 'A' && map[i][j] <= 'Z' || map[i][j] == '#'{
                                bfs(i, j);
                            }

                        }

                    }


                    ans 
            = -1;
                    
                    
            for(i = 0; i < n; i++{

                        
            for(j = 0; j < m; j++{

                            
            if(map[i][j] >= 'A' && map[i][j] <= 'Z'{
                                
            int ty = BFS(i, j, map[i][j]-'A'+1);
                                
            if(ty != -1{
                                    
            if(ty < ans || ans == -1)
                                        ans 
            = ty;
                                }

                            }

                            
            if(map[i][j] == '#'{
                                
            int ty = BFS(i, j, 0);    
                                
            if(ty != -1{
                                    
            if(ty < ans || ans == -1)
                                        ans 
            = ty;
                                }

                            }

                        }

                    }


                    
            if(ans == -1)
                        printf(
            "IMPOSSIBLE\n");
                    
            else
                        printf(
            "%d\n", ans);

                }

                
            return 0;
            }

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

            亚洲精品高清久久| 香蕉久久永久视频| 欧美va久久久噜噜噜久久| 国内精品久久久久影院日本| 丰满少妇高潮惨叫久久久| 久久精品99无色码中文字幕| 久久综合色老色| 欧美综合天天夜夜久久| 久久久久99精品成人片牛牛影视| 三级三级久久三级久久| 久久国产精品-久久精品| 午夜精品久久久久久久无码| 久久久久亚洲精品天堂| 狠狠久久综合伊人不卡| 九九精品99久久久香蕉| 日本亚洲色大成网站WWW久久| 久久久无码精品亚洲日韩蜜臀浪潮| 国产成人精品久久二区二区| 久久久久亚洲AV无码专区网站| 午夜精品久久久久久99热| 亚洲精品乱码久久久久久蜜桃图片 | 久久久久亚洲精品无码蜜桃| 久久国产乱子伦精品免费午夜| 久久久久久久97| 久久这里只有精品视频99| 精品999久久久久久中文字幕| 国产精品美女久久福利网站| 久久精品国产精品亚洲| 99久久免费国产精品| 久久精品国产亚洲AV无码偷窥| 亚洲欧美成人久久综合中文网 | 国产欧美一区二区久久| 亚洲精品无码久久久久| 久久久久亚洲av成人网人人软件| 国产成人精品久久亚洲高清不卡| 久久久久久久久久久久中文字幕 | 国产毛片久久久久久国产毛片| 韩国无遮挡三级久久| 久久久久成人精品无码中文字幕| 久久午夜无码鲁丝片秋霞| 久久99热这里只有精品66|