九九精品99久久久香蕉,久久香综合精品久久伊人,一日本道伊人久久综合影

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.

----樣例輸入：

9 13

#############

#####.#.#.#.#

..#

#.#.#.#.#.#.#

#.#

.#.#

#.#.#.#.#.#.#

..#

#####.#######

4 6

#.####

#.#.##

######

----樣例輸出：

-1

----分析：

搜索即可，只是注意擴(kuò)展方式，左或右可以時(shí)，不可向前。

/**********************************************************

版本五：

AC 0MS

SPFA 求最短路。

出口不止一個(gè)，邊界上的可達(dá)點(diǎn)都是出口。

#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;

}

/**********************************************************

版本四：

發(fā)現(xiàn)之前對(duì) “You never turn around and go back!”理解有誤，只是不能后退而已。

寬度優(yōu)先搜索。

#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;

}

/**********************************************************

版本三：

SPFA 求最短路。

錯(cuò)誤“從目標(biāo)點(diǎn)可離開地圖”修正。

#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;

}

/**********************************************************

版本二：

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 閱讀(640) 評(píng)論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè)

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 微軟2014實(shí)習(xí)生及秋令營技術(shù)類職位在線測(cè)試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數(shù)碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊(cè)

ACM

AI

LaTeX

安全

編程語言

好有道理

技術(shù)

開源

科學(xué)

數(shù)學(xué)

圖形圖像

文化

問題（練習(xí)＆有趣）

資源

最新隨筆

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

EOJ 1780 Escape