• <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>

            TC-SRM-233-1000pt BFS

            Posted on 2009-11-25 11:39 rikisand 閱讀(282) 評論(0)  編輯 收藏 引用 所屬分類: TopcoderAlgorithm
            繼續是misof 數字教學里面的習題~ 第一篇的最后一道題了~
            Problem Statement

            You are in a maze containing revolving doors. The doors can be turned 90 degrees by pushing against them in either direction. You are to find a route from the start square to the end square that involves revolving as few doors as possible. Given a map of the maze, determine the fewest number of door revolutions necessary to get from the start to the end.

            In the map:

               ' ': empty space
               '#': wall
               'O': center of a revolving door (letter "oh", not zero)
               '-': horizontal door (always adjacent to a 'O')
               '|': vertical door (always adjacent to a 'O')
               'S': start square
               'E': end square
            

            Each revolving door will always be oriented horizontally (with two horizontal segments) or vertically (with two vertical segments):

                |
                O  or  -O-
                |
            

            Doors can be revolved 90 degrees by moving onto a door segment from any of the 4 squares diagonally adjacent to the door center, i.e., the 'X' characters below:

               X|X     X X
                O  or  -O-
               X|X     X X
            

            Here is an example map:

                    ###
                    #E#
                   ## #
                ####  ##
                # S -O-#
                # ###  #
                #      #
                ########
            

            In this example, 2 door revolutions are necessary to get from 'S' to 'E'. The first turn is shown here:

                    ###         ###
                    #E#         #E#
                   ## #        ## #
                ####  ##    #### |##
                # S -O-#    # S  OX#
                # ### X#    # ###| #
                #      #    #      #
                ########    ########
            

            And the second turn is shown here:

                    ###         ###
                    #E#         #E#
                   ## #        ## #
                ####X|##    #### X##
                # S  O #    # S -O-#
                # ###| #    # ###  #
                #      #    #      #
                ########    ########
            

            Your method should return an int, the minimum number of door revolutions necessary to get from the start square to the end square. If there is no way to reach the end square, return -1.

            Definition

            Class:
            RevolvingDoors

            Method:
            turns

            Parameters:
            vector <string>

            Returns:
            int

            Method signature:
            int turns(vector <string> map)

            (be sure your method is public)

            Notes

            -
            Assume that all squares off the edge of the map are walls.

            Constraints

            -
            map will contain between 3 and 50 elements, inclusive.

            -
            Each element of map will contain between 3 and 50 characters, inclusive.

            -
            Each element of map will contain the same number of characters.

            -
            Each character in map will be one of 'S', 'E', 'O', '-', '|', '#', and ' ' (space).

            -
            There will be exactly one 'S' and one 'E' in map.

            -
            There will be between 1 and 10 doors, inclusive, and they will be formatted in map as described in the problem statement.

            -
            No two doors will be close enough for any part of them to occupy the same square.

            -
            It is not allowed for a door to be blocked and unable to turn. There will not be any walls in any of the 4 squares immediately adjacent to the center of a door, nor will a door be on the edge of the map.

            關鍵是門的狀態表示,參考了網站上的代碼,挑了一個比較簡練的,用的優先級隊列。寫完調好發現TLE 囧~ copy出網站上的再run依然TLE``` ``` 看了下發現現在的system testing 比原來增加了幾個測試用例~~~   于是找出misof大牛的解法,發現對狀態處理一樣的~~~只不過用了memo和deque,省去了優先級隊列調整的時間開銷,改好了就pass了~ 上代碼~~:
            Code Snippet
            using namespace std;
            typedef long long int64;  
            typedef vector<int> VI;
            typedef vector<string> VS;
            #define inf 1000000
            #define REP(i,n) for(int (i)=(0);((i)<(n));++(i))
            template<class T> inline void checkmin(T &a,const T &b) { if (b<a) a=b; }
            template<class T> inline void checkmax(T &a,const T &b) { if (b>a) a=b; }
            int dr[]={-1,0,1,0};
            int dc[]={0,1,0,-1};
            struct state{state(int x,int y,int z,int s):r(x),c(y),doorstate(z),best(s){}int r;int c;int doorstate;int best;};
            int memo[56][56][1<<11];
            class RevolvingDoors
            {
                    public:
                    int turns(vector <string> mp)
                    {
                         int x=mp.size()+2;int y=mp[0].size()+2;
                         int sr,sc,er,ec,cnt=0,doorInit=0;
                         REP(i,x-2)mp[i]='#'+mp[i]+'#';                //trick:modify the pattern to make it easy to loop
                         mp.insert(mp.begin(),string(58,'#'));
                         mp.push_back(string(58,'#'));
                         REP(i,x)REP(j,y)if(mp[i][j]=='S'){mp[i][j]=' ';sr=i;sc=j;}else if(mp[i][j]=='E'){mp[i][j]=' ';er=i;ec=j;}
                         REP(i,x)REP(j,y)if(mp[i][j]=='O'){if(mp[i-1][j]=='|')doorInit|=(1<<cnt);
                            mp[i-1][j]=mp[i+1][j] = 100 + cnt*2 +1;    //use the content in the box to identify the door number,and the door pos
                            mp[i][j-1]=mp[i][j+1] = 100 + cnt*2 ;    //if pos==0 it means this box is on the left or right of the door
                            cnt++; mp[i][j]='#';
                         }
                         REP(i,x)REP(j,y)REP(t,1<<cnt) memo[i][j][t] = inf;    //init the memo
                         deque<state> Q; Q.push_back(state(sr,sc,doorInit,0));
                         while(!Q.empty()){
                            state now=Q.front();Q.pop_front();
                            int r=now.r  , c=now.c  , door=now.doorstate , b=now.best;
                            if( memo[r][c][door] < b)continue;    //no better ,no vist
                            REP(dir,4){                            //try four direction
                                int nr=r+dr[dir],nc=c+dc[dir];
                                if(mp[nr][nc]==' '){
                                    if(memo[nr][nc][door] > b){ memo[nr][nc][door]=b;Q.push_back(state(nr,nc,door,b));}
                                }
                                else if(mp[nr][nc]=='#')continue;
                                else{                            //if we come to a box near to the door-mid
                                    int doornum=(mp[nr][nc]-100)/2;int open=(mp[nr][nc]-100)%2;    
                                    if( ((door>>doornum)&1) != open){    //lucily,the box is empty
                                        if(memo[nr][nc][door] > b){memo[nr][nc][door] = b;Q.push_back(state(nr,nc,door,b));}
                                    }        
                                    else {                                // the box has a door
                                        if(open==0 && dr[dir]==0) continue;    //try to define the relative pos between the direction and the box
                                        if(open==1 && dc[dir]==0) continue;    //also ~ if we cannot push the door we give up
                                        int ndoor=door^(1<<doornum);    //we can go into the box if we push the door ~
                                        if(memo[nr][nc][ndoor] > b+1 ){memo[nr][nc][ndoor] = b+1 ;Q.push_back(state(nr,nc,ndoor,b+1));}
                                    }
                                }
                            }
                         }
                         int ans=inf;
                         REP(i,1<<cnt){ //loop to check the best ans~
                             if(memo[er][ec][i]<ans){ans=memo[er][ec][i];cout<<er<<" "<<ec<<" "<<hex<<i<<endl;}
                         }
                         if(ans == inf) return -1;
                         else return ans;
                    }

            中文copy是亂碼···囧啊~~ 俺的破爛英文注釋啊~~~

            久久国产成人| 91久久精品国产免费直播| 国产福利电影一区二区三区,免费久久久久久久精 | 久久婷婷人人澡人人| 蜜臀久久99精品久久久久久| 久久人人爽人人澡人人高潮AV| 久久免费大片| 久久一日本道色综合久久| 久久精品男人影院| 中文精品99久久国产| 国产精品久久久久…| 看全色黄大色大片免费久久久| 欧美与黑人午夜性猛交久久久 | 久久久久免费看成人影片| 久久国产成人午夜aⅴ影院| 久久人人爽人人爽人人片AV高清 | 久久99精品国产自在现线小黄鸭 | 99久久国产宗和精品1上映| 国产精品久久久久一区二区三区| 亚洲成av人片不卡无码久久| 国产精品欧美久久久天天影视 | 久久久噜噜噜久久熟女AA片| 久久综合狠狠综合久久激情 | 久久人人爽人人爽AV片| 久久久噜噜噜www成人网| 亚洲伊人久久成综合人影院 | 伊人色综合久久天天| 中文字幕乱码久久午夜| 久久精品国产99久久丝袜| 人人狠狠综合久久亚洲婷婷| 精品久久久久久久久午夜福利| 欧美日韩中文字幕久久久不卡| 欧美久久综合性欧美| 久久精品aⅴ无码中文字字幕不卡| 亚洲精品无码久久毛片| 欧美与黑人午夜性猛交久久久| 中文字幕成人精品久久不卡 | 伊人久久免费视频| 狠狠色丁香久久综合五月| 99国产精品久久久久久久成人热| 久久人人爽人人爽人人爽|