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

            coreBugZJ

            此 blog 已棄。

            EOJ 1780 Escape

            /*
            EOJ 1780 Escape


            ----問題描述:

            You find yourself trapped in a large rectangular room, made up of large square tiles; some
            are accessible, others are blocked by obstacles or walls. With a single step, you can move
            from one tile to another tile if it is horizontally or vertically adjacent (i.e. you cannot move
            diagonally).
            To shake off any people following you, you do not want to move in a straight line. In fact,
            you want to take a turn at every opportunity, never moving in any single direction longer
            than strictly necessary. This means that if, for example, you enter a tile from the south,
            you will turn either left or right, leaving to the west or the east. Only if both directions
            are blocked, will you move on straight ahead. You never turn around and go back!
            Given a map of the room and your starting location, figure out how long it will take you
            to escape (that is: reach the edge of the room).


            ----輸入:

            On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test
            case:
            1. a line with two integers separated by a space, h and w (1 <= h,w <= 80), the height
            and width of the room;
            2. then h lines, each containing w characters, describing the room. Each character is one
            of . (period; an accessible space), # (a blocked space) or @ (your starting location).
            There will be exactly one @ character in each room description.


            ----輸出:

            For each test case:
            1. A line with an integer: the minimal number of steps necessary to reach the edge of
            the room, or -1 if no escape is possible.


            ----樣例輸入:

            2
            9 13
            #############
            #@.#
            #####.#.#.#.#
            #..#
            #.#.#.#.#.#.#
            #.#.#.#
            #.#.#.#.#.#.#
            #..#
            #####.#######
            4 6
            #.####
            #.#.##
            #@#
            ######


            ----樣例輸出:

            31
            -1


            ----分析:

            搜索即可,只是注意擴展方式,左或右可以時,不可向前。

            */




            /**********************************************************
            版本五:
            AC 0MS
            SPFA 求最短路。
            出口不止一個,邊界上的可達點都是出口。
            */


            #include 
            <stdio.h>
            #include 
            <string.h>


            #define  L    89
            #define  INF  0x3f3f3f3f

            #define  CAN   '.'


            #define  T  4
            int di[] = -1010 };
            int dj[] = 010-1 };


            int  h, w;
            int  srcI, srcJ, dstI, dstJ;
            char map[ L ][ L ];

            int spfa() {
            #define  QL  (L*L*T)
                    
            static int queI[ QL ], queJ[ QL ], queD[ QL ], inq[ L ][ L ][ T ], dist[ L ][ L ][ T ];
                    
            int qh = 0, qt = 0, i, j, d, chg, ni, nj, nd, ans;
                    memset( dist, 
            0x3fsizeof(dist) );
                    memset( inq,  
            0,    sizeof(inq)  );
                    
            for ( i = 0; i < T; ++i ) {
                            queI[ qt ] 
            = srcI;
                            queJ[ qt ] 
            = srcJ;
                            queD[ qt ] 
            = i;
                            inq[ srcI ][ srcJ ][ i ] 
            = 1;
                            dist[ srcI ][ srcJ ][ i ] 
            = 0;
                            qt 
            = (qt + 1% QL;
                    }

                    
            while ( qh != qt ) {
                            i 
            = queI[ qh ];
                            j 
            = queJ[ qh ];
                            d 
            = queD[ qh ];
                            inq[ i ][ j ][ d ] 
            = 0;
                            qh 
            = (qh + 1% QL;

                            chg 
            = 0;

            #define  UPDATE if ( dist[ i ][ j ][ d ] + 1 < dist[ ni ][ nj ][ nd ] ) { \
                                    dist[ ni ][ nj ][ nd ] 
            = dist[ i ][ j ][ d ] + 1; \
                                    
            if ( ! inq[ ni ][ nj ][ nd ] ) { \
                                            inq[ ni ][ nj ][ nd ] 
            = 1; \
                                            queI[ qt ] 
            = ni; \
                                            queJ[ qt ] 
            = nj; \
                                            queD[ qt ] 
            = nd; \
                                            qt 
            = (qt + 1% QL; \
                                    }
             \
                            }

                            
            #define  MOD    ni = i + di[ nd ]; \
                            nj 
            = j + dj[ nd ]; \
                            
            if ( CAN == map[ ni ][ nj ] ) { \
                                    chg 
            = 1; \
                                    UPDATE \
                            }


                            nd 
            = (d + 1% T;
                            MOD

                            nd 
            = (d + T - 1% T;
                            MOD

                            
            if ( 0 == chg ) {
                                    nd 
            = d;
                                    MOD
                            }

                    }


            #define  UPANS \
                    
            for ( d = 0; d < T; ++d ) { \
                            
            if ( ans > dist[ dstI ][ dstJ ][ d ] ) { \
                                    ans 
            = dist[ dstI ][ dstJ ][ d ]; \
                            }
             \
                    }


                    ans 
            = INF;
                    
            for ( j = 1; j <= w; ++j ) {
                            
            if ( '.' == map[ 1 ][ j ] ) {
                                    dstI 
            = 1;
                                    dstJ 
            = j;
                                    UPANS
                            }

                            
            if ( '.' == map[ h ][ j ] ) {
                                    dstI 
            = h;
                                    dstJ 
            = j;
                                    UPANS
                            }

                    }

                    
            for ( i = 1; i <= h; ++i ) {
                            
            if ( '.' == map[ i ][ 1 ] ) {
                                    dstI 
            = i;
                                    dstJ 
            = 1;
                                    UPANS
                            }

                            
            if ( '.' == map[ i ][ w ] ) {
                                    dstI 
            = i;
                                    dstJ 
            = w;
                                    UPANS
                            }

                    }


                    
            if ( INF == ans ) {
                            ans 
            = -1;
                    }

                    
            return ans;
            }

            int main() {
                    
            int td;
                    
            int i, j;
                    scanf( 
            "%d"&td );
                    
            while ( td-- > 0 ) {
                            scanf( 
            "%d%d"&h, &w );
                            gets( map[ 
            0 ] );
                            memset( map, 
            '#'sizeof(map) );
                            
            for ( i = 1; i <= h; ++i ) {
                                    gets( map[ i ] 
            + 1 );
                                    
            for ( j = 1; j <= w; ++j ) {
                                            
            if ( '@' == map[ i ][ j ] ) {
                                                    srcI 
            = i;
                                                    srcJ 
            = j;
                                                    map[ i ][ j ] 
            = '.';
                                            }

                                    }

                            }


                            printf( 
            "%d\n", spfa() );
                    }

                    
            return 0;
            }



            /**********************************************************
            版本四:
            WA
            發現之前對 “You never turn around and go back!”理解有誤,只是不能后退而已。
            寬度優先搜索。

            */

            /*
            #include <stdio.h>
            #include <string.h>


            #define  L    89
            #define  INF  0x3f3f3f3f

            #define  CAN   '.'


            #define  T  4
            int di[] = { -1, 0, 1, 0 };
            int dj[] = { 0, 1, 0, -1 };


            int  h, w;
            int  srcI, srcJ, dstI, dstJ;
            char map[ L ][ L ];

            int bfs() {
            #define  QL  (L*L*T)
                    static int queI[ QL ], queJ[ QL ], queD[ QL ], inq[ L ][ L ][ T ], dist[ L ][ L ][ T ];
                    int qh = 0, qt = 0, i, j, d, chg, ni, nj, nd, ans;
                    memset( dist, 0x3f, sizeof(dist) );
                    memset( inq,  0,    sizeof(inq)  );
                    i = srcI;
                    j = srcJ;
                    for ( nd = 0; nd < T; ++nd ) {
                            ni = i + di[ nd ];
                            nj = j + dj[ nd ];
                            if ( CAN == map[ ni ][ nj ] ) {
                                    queI[ qt ] = ni;
                                    queJ[ qt ] = nj;
                                    queD[ qt ] = nd;
                                    inq[ ni ][ nj ][ nd ] = 1;
                                    dist[ ni ][ nj ][ nd ] = 1;
                                    ++qt;
                            }
                    }
                    while ( qh != qt ) {
                            i = queI[ qh ];
                            j = queJ[ qh ];
                            d = queD[ qh ];
                            ++qh;

                            chg = 0;

            #define  UPDATE do { \
                                    dist[ ni ][ nj ][ nd ] = dist[ i ][ j ][ d ] + 1; \
                                    inq[ ni ][ nj ][ nd ] = 1; \
                                    queI[ qt ] = ni; \
                                    queJ[ qt ] = nj; \
                                    queD[ qt ] = nd; \
                                    ++qt; \
                            } while (0)

            #define  MOD    do { \
                                    ni = i + di[ nd ]; \
                                    nj = j + dj[ nd ]; \
                                    if ( CAN == map[ni][nj] ) { \
                                            chg = 1; \
                                            if ( ! inq[ni][nj][nd] ) { \
                                                    UPDATE; \
                                            } \
                                    } \
                            } while (0)

                            nd = (d + 1) % T;
                            MOD;

                            nd = (d + T - 1) % T;
                            MOD;

                            if ( 0 == chg ) {
                                    nd = d;
                                    MOD;
                            }
                    }

                    ans = dist[ dstI ][ dstJ ][ 0 ];
                    for ( d = 1; d < T; ++d ) {
                            if ( ans > dist[ dstI ][ dstJ ][ d ] ) {
                                    ans = dist[ dstI ][ dstJ ][ d ];
                            }
                    }
                    if ( INF == ans ) {
                            ans = -1;
                    }
                    return ans;
            }

            int solve() {
                    if ( (srcI == dstI) && (srcJ == dstJ) ) {
                            return 0;
                    }
                    return bfs();
            }

            int main() {
                    int td;
                    int i, j;
                    scanf( "%d", &td );
                    while ( td-- > 0 ) {
                            scanf( "%d%d", &h, &w );
                            gets( map[ 0 ] );
                            memset( map, '#', sizeof(map) );
                            for ( i = 1; i <= h; ++i ) {
                                    gets( map[ i ] + 1 );
                                    map[ i ][ w+1 ] = '#';
                                    for ( j = 1; j <= w; ++j ) {
                                            if ( '@' == map[ i ][ j ] ) {
                                                    srcI = i;
                                                    srcJ = j;
                                                    map[ i ][ j ] = '.';
                                            }
                                    }
                            }
                            dstI = -1;
                            for ( j = 1; (0 > dstI) && (j <= w); ++j ) {
                                    if ( '.' == map[ 1 ][ j ] ) {
                                            dstI = 1;
                                            dstJ = j;
                                    }
                                    if ( '.' == map[ h ][ j ] ) {
                                            dstI = h;
                                            dstJ = j;
                                    }
                            }
                            for ( i = 1; (0 > dstI) && (i <= h); ++i ) {
                                    if ( '.' == map[ i ][ 1 ] ) {
                                            dstI = i;
                                            dstJ = 1;
                                    }
                                    if ( '.' == map[ i ][ w ] ) {
                                            dstI = i;
                                            dstJ = w;
                                    }
                            }

                            printf( "%d\n", solve() );
                    }
                    return 0;
            }
            */



            /**********************************************************
            版本三:
            WA
            SPFA 求最短路。
            錯誤“從目標點可離開地圖”修正。
            */

            /*
            #include <stdio.h>
            #include <string.h>


            #define  L    89
            #define  INF  0x3f3f3f3f

            #define  CAN   '.'


            #define  T  4
            int di[] = { -1, 0, 1, 0 };
            int dj[] = { 0, 1, 0, -1 };


            int  h, w;
            int  srcI, srcJ, dstI, dstJ;
            char map[ L ][ L ];

            int spfa() {
            #define  QL  (L*L*T)
                    static int queI[ QL ], queJ[ QL ], queD[ QL ], inq[ L ][ L ][ T ], dist[ L ][ L ][ T ];
                    int qh = 0, qt = 0, i, j, d, chg, ni, nj, nd, ans;
                    memset( dist, 0x3f, sizeof(dist) );
                    memset( inq,  0,    sizeof(inq)  );
                    for ( i = 0; i < T; ++i ) {
                            queI[ qt ] = srcI;
                            queJ[ qt ] = srcJ;
                            queD[ qt ] = i;
                            inq[ srcI ][ srcJ ][ i ] = 1;
                            dist[ srcI ][ srcJ ][ i ] = 0;
                            qt = (qt + 1) % QL;
                    }
                    while ( qh != qt ) {
                            i = queI[ qh ];
                            j = queJ[ qh ];
                            d = queD[ qh ];
                            inq[ i ][ j ][ d ] = 0;
                            qh = (qh + 1) % QL;

                            chg = 0;

            #define  UPDATE if ( dist[ i ][ j ][ d ] + 1 < dist[ ni ][ nj ][ nd ] ) { \
                                    dist[ ni ][ nj ][ nd ] = dist[ i ][ j ][ d ] + 1; \
                                    if ( ! inq[ ni ][ nj ][ nd ] ) { \
                                            inq[ ni ][ nj ][ nd ] = 1; \
                                            queI[ qt ] = ni; \
                                            queJ[ qt ] = nj; \
                                            queD[ qt ] = nd; \
                                            qt = (qt + 1) % QL; \
                                    } \
                            }
                            
            #define  MOD    ni = i + di[ nd ]; \
                            nj = j + dj[ nd ]; \
                            if ( CAN == map[ ni ][ nj ] ) { \
                                    chg = 1; \
                                    UPDATE \
                            }

                            nd = (d + 1) % T;
                            MOD

                            nd = (d + T - 1) % T;
                            MOD

                            if ( 0 == chg ) {
                                    nd = d;
                                    MOD
                            }
                    }

                    ans = dist[ dstI ][ dstJ ][ 0 ];
                    for ( d = 1; d < T; ++d ) {
                            if ( ans > dist[ dstI ][ dstJ ][ d ] ) {
                                    ans = dist[ dstI ][ dstJ ][ d ];
                            }
                    }
                    if ( INF == ans ) {
                            ans = -1;
                    }
                    return ans;
            }

            int main() {
                    int td;
                    int i, j;
                    scanf( "%d", &td );
                    while ( td-- > 0 ) {
                            scanf( "%d%d", &h, &w );
                            gets( map[ 0 ] );
                            memset( map, '#', sizeof(map) );
                            for ( i = 1; i <= h; ++i ) {
                                    gets( map[ i ] + 1 );
                                    for ( j = 1; j <= w; ++j ) {
                                            if ( '@' == map[ i ][ j ] ) {
                                                    srcI = i;
                                                    srcJ = j;
                                                    map[ i ][ j ] = '.';
                                            }
                                    }
                            }
                            dstI = -1;
                            for ( j = 1; (0 > dstI) && (j <= w); ++j ) {
                                    if ( '.' == map[ 1 ][ j ] ) {
                                            dstI = 1;
                                            dstJ = j;
                                    }
                                    if ( '.' == map[ h ][ j ] ) {
                                            dstI = h;
                                            dstJ = j;
                                    }
                            }
                            for ( i = 1; (0 > dstI) && (i <= h); ++i ) {
                                    if ( '.' == map[ i ][ 1 ] ) {
                                            dstI = i;
                                            dstJ = 1;
                                    }
                                    if ( '.' == map[ i ][ w ] ) {
                                            dstI = i;
                                            dstJ = w;
                                    }
                            }

                            printf( "%d\n", spfa() );
                    }
                    return 0;
            }
            */



            /**********************************************************
            版本二:
            WA
            SPFA 求最短路。
            */

            /*
            #include <stdio.h>
            #include <string.h>


            #define  L    89
            #define  INF  0x3f3f3f3f

            #define  CAN   '.'


            #define  T  4
            int di[] = { -1, 0, 1, 0 };
            int dj[] = { 0, 1, 0, -1 };


            int  h, w;
            int  srcI, srcJ, dstI, dstJ;
            char map[ L ][ L ];

            int spfa() {
            #define  QL  (L*L*T)
                    static int queI[ QL ], queJ[ QL ], queD[ QL ], inq[ L ][ L ][ T ], dist[ L ][ L ][ T ];
                    int qh = 0, qt = 0, i, j, d, chg, ni, nj, nd, ans;
                    memset( dist, 0x3f, sizeof(dist) );
                    memset( inq,  0,    sizeof(inq)  );
                    for ( i = 0; i < T; ++i ) {
                            queI[ qt ] = srcI;
                            queJ[ qt ] = srcJ;
                            queD[ qt ] = i;
                            inq[ srcI ][ srcJ ][ i ] = 1;
                            dist[ srcI ][ srcJ ][ i ] = 0;
                            qt = (qt + 1) % QL;
                    }
                    while ( qh != qt ) {
                            i = queI[ qh ];
                            j = queJ[ qh ];
                            d = queD[ qh ];
                            inq[ i ][ j ][ d ] = 0;
                            qh = (qh + 1) % QL;

                            chg = 0;

            #define  UPDATE if ( dist[ i ][ j ][ d ] + 1 < dist[ ni ][ nj ][ nd ] ) { \
                                    dist[ ni ][ nj ][ nd ] = dist[ i ][ j ][ d ] + 1; \
                                    if ( ! inq[ ni ][ nj ][ nd ] ) { \
                                            inq[ ni ][ nj ][ nd ] = 1; \
                                            queI[ qt ] = ni; \
                                            queJ[ qt ] = nj; \
                                            queD[ qt ] = nd; \
                                            qt = (qt + 1) % QL; \
                                    } \
                            }
                            
            #define  MOD    ni = i + di[ nd ]; \
                            nj = j + dj[ nd ]; \
                            if ( CAN == map[ ni ][ nj ] ) { \
                                    chg = 1; \
                                    UPDATE \
                            }

                            nd = (d + 1) % T;
                            MOD

                            nd = (d + T - 1) % T;
                            MOD

                            if ( 0 == chg ) {
                                    nd = d;
                                    MOD
                            }
                    }

                    ans = dist[ dstI ][ dstJ ][ 0 ];
                    for ( d = 1; d < T; ++d ) {
                            if ( ans > dist[ dstI ][ dstJ ][ d ] ) {
                                    ans = dist[ dstI ][ dstJ ][ d ];
                            }
                    }
                    if ( INF == ans ) {
                            ans = -1;
                    }
                    return ans;
            }

            int main() {
                    int td;
                    int i, j;
                    scanf( "%d", &td );
                    while ( td-- > 0 ) {
                            scanf( "%d%d", &h, &w );
                            gets( map[ 0 ] );
                            for ( i = 0; i < h; ++i ) {
                                    gets( map[ i ] );
                                    for ( j = 0; j < w; ++j ) {
                                            if ( '@' == map[ i ][ j ] ) {
                                                    srcI = i;
                                                    srcJ = j;
                                            }
                                    }
                            }
                            dstI = -1;
                            for ( j = 0; (0 > dstI) && (j < w); ++j ) {
                                    if ( '.' == map[ 0 ][ j ] ) {
                                            dstI = 0;
                                            dstJ = j;
                                    }
                                    if ( '.' == map[ h-1 ][ j ] ) {
                                            dstI = h - 1;
                                            dstJ = j;
                                    }
                            }
                            for ( i = 0; (0 > dstI) && (i < h); ++i ) {
                                    if ( '.' == map[ i ][ 0 ] ) {
                                            dstI = i;
                                            dstJ = 0;
                                    }
                                    if ( '.' == map[ i ][ w-1 ] ) {
                                            dstI = i;
                                            dstJ = w - 1;
                                    }
                            }

                            printf( "%d\n", spfa() );
                    }
                    return 0;
            }
            */




            /**********************************************************
            版本一:
            TLE
            DFS 窮舉所有,取最小值。
            */

            /*
            #include <stdio.h>
            #include <string.h>


            #define  L    89
            #define  INF  0x3f3f3f3f

            #define  CAN   '.'


            #define  T  4
            int di[] = { -1, 0, 1, 0 };
            int dj[] = { 0, 1, 0, -1 };


            int  h, w;
            int  srcI, srcJ, dstI, dstJ;
            char map[ L ][ L ];
            int  ans, tmp;
            int  walk[ L ][ L ];

            void dfs( int i, int j, int dir ) {
                    int ni, nj, chg = 0;
                    if ( (walk[ i ][ j ]) || (tmp >= ans) ) {
                            return;
                    }
                    if ((i == dstI) && (j == dstJ)) {
                            if (tmp < ans) {
                                    ans = tmp;
                            }
                            return;
                    }
                    walk[ i ][ j ] = 1;
                    ++tmp;

                    dir = (dir + 1) % T;
                    ni = i + di[ dir ];
                    nj = j + dj[ dir ];
                    if ( CAN == map[ ni ][ nj ] ) {
                            chg = 1;
                            dfs( ni, nj, dir);
                    }

                    dir = (dir + T - 2) % T;
                    ni = i + di[ dir ];
                    nj = j + dj[ dir ];
                    if ( CAN == map[ ni ][ nj ] ) {
                            chg = 1;
                            dfs( ni, nj, dir);
                    }

                    if ( 0 == chg ) {
                            dir = (dir + 1) % T;
                            ni = i + di[ dir ];
                            nj = j + dj[ dir ];
                            if ( CAN == map[ ni ][ nj ] ) {
                                    dfs( ni, nj, dir);
                            }
                    }

                    --tmp;
                    walk[ i ][ j ] = 0;
            }

            int main() {
                    int td;
                    int i, j;
                    scanf( "%d", &td );
                    while ( td-- > 0 ) {
                            scanf( "%d%d", &h, &w );
                            gets( map[ 0 ] );
                            for ( i = 0; i < h; ++i ) {
                                    gets( map[ i ] );
                                    for ( j = 0; j < w; ++j ) {
                                            if ( '@' == map[ i ][ j ] ) {
                                                    srcI = i;
                                                    srcJ = j;
                                            }
                                    }
                            }
                            dstI = -1;
                            for ( j = 0; (0 > dstI) && (j < w); ++j ) {
                                    if ( '.' == map[ 0 ][ j ] ) {
                                            dstI = 0;
                                            dstJ = j;
                                    }
                                    if ( '.' == map[ h-1 ][ j ] ) {
                                            dstI = h - 1;
                                            dstJ = j;
                                    }
                            }
                            for ( i = 0; (0 > dstI) && (i < h); ++i ) {
                                    if ( '.' == map[ i ][ 0 ] ) {
                                            dstI = i;
                                            dstJ = 0;
                                    }
                                    if ( '.' == map[ i ][ w-1 ] ) {
                                            dstI = i;
                                            dstJ = w - 1;
                                    }
                            }

                            memset( walk, 0, sizeof(walk) );
                            ans = INF;
                            tmp = 0;
                            for ( i = 0; i < T; ++i ) {
                                    dfs( srcI, srcJ, i );
                            }
                            printf( "%d\n", ((INF != ans) ? ans : (-1)) );
                    }
                    return 0;
            }
            */

            posted on 2012-04-21 16:40 coreBugZJ 閱讀(648) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm課內作業

            久久久中文字幕日本| 久久97精品久久久久久久不卡| 久久综合欧美成人| 久久久久久国产a免费观看不卡| 久久综合视频网站| 国产精品久久久久久久| 人妻丰满?V无码久久不卡| 无码国内精品久久人妻| 国产精品亚洲美女久久久| 亚洲精品白浆高清久久久久久| 日本精品久久久久中文字幕8| 热久久视久久精品18| 欧美久久精品一级c片片| 18岁日韩内射颜射午夜久久成人| 国产高潮国产高潮久久久91 | 一本一本久久A久久综合精品| 国产一级做a爰片久久毛片| 久久久久久久久波多野高潮| 久久综合久久综合九色| 精品国产VA久久久久久久冰| 亚洲精品无码久久毛片| 99久久综合狠狠综合久久| 九九精品99久久久香蕉| 久久中文字幕人妻熟av女| 久久午夜综合久久| 久久996热精品xxxx| 久久夜色精品国产噜噜亚洲AV| 一级a性色生活片久久无| 久久丝袜精品中文字幕| 国产精品成人99久久久久 | 久久精品国产黑森林| 日本精品久久久久中文字幕| 久久青草国产精品一区| 国内精品久久国产大陆| 丰满少妇人妻久久久久久| 久久精品中文騷妇女内射| 亚洲人成伊人成综合网久久久| 久久精品国产亚洲AV不卡| 一本久久a久久精品亚洲| 久久久久99精品成人片直播| 色婷婷综合久久久中文字幕|