• <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課內作業

            久久亚洲国产成人影院网站| 精品无码久久久久久尤物| 久久久久综合国产欧美一区二区| 久久精品视屏| 精品久久久久久亚洲精品| 久久久精品视频免费观看| 久久综合久久自在自线精品自| 久久国产精品久久精品国产| 四虎影视久久久免费观看| 久久久久久人妻无码| 欧美与黑人午夜性猛交久久久| 国产69精品久久久久777| 亚洲欧美精品一区久久中文字幕 | 伊人久久综合成人网| 2021少妇久久久久久久久久| 精品国产乱码久久久久软件| 国内精品久久久久久不卡影院| 国产午夜精品久久久久免费视| 国内精品伊人久久久久妇| 国内精品久久久久久中文字幕| 99久久成人国产精品免费| 色偷偷88888欧美精品久久久| 欧美精品丝袜久久久中文字幕| 亚洲国产成人久久综合碰碰动漫3d| 久久影院综合精品| 久久婷婷色综合一区二区| 伊人久久无码精品中文字幕| 伊人热热久久原色播放www| 性做久久久久久久久| 欧美性猛交xxxx免费看久久久| 欧美精品福利视频一区二区三区久久久精品 | 色噜噜狠狠先锋影音久久| 国产V亚洲V天堂无码久久久| 人妻精品久久久久中文字幕69| 久久精品国产亚洲AV忘忧草18| 精品久久久久成人码免费动漫| 亚洲日本va午夜中文字幕久久| 久久黄色视频| 狠狠色丁香婷婷久久综合五月| 国产免费久久精品99re丫y| 久久伊人精品一区二区三区|