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[] = { -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
                }
        }

#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 阅读(617) 评论(0)  编辑 收藏 引用 所属分类: ACM 、Algorithm 、课内作业


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理