首页 > ACM题库 > HDU-杭电 > hdu 2332 Hypertheseus-BFS-[解题报告]hoj
2014
01-05

hdu 2332 Hypertheseus-BFS-[解题报告]hoj

Hypertheseus

问题描述 :

For one of their clients, ACM prepares a TV advertisement that features ancient heroes, for example Prometheus, Achilles, Odysseus and many others. To demonstrate how difficult was life for these heroes, ACMruns computer simulations of their most famous tasks. In this problem, we will try to solve the problem of Theseus.

Theseus was an Athenian hero who killed Minotaur, the half-man, half-bull monster residing in an inescapable Labyrinth constructed by Daedalus. The hardest part of Theseus’ task was not killing the monster ― the legend says Minotaur was just sleeping when Theseus came to him. Thus, the hero was able to batter the monster with his bare hands. But then the real challenge came: to find the way out. As you may know, Ariadne, beautiful daughter of king Minos, played an important role in this part. But that’s a different story.

As the technology advanced a lot since the ancient times, there are several important differences in today’s simulations:

1. Labyrinth-making skills advanced as well. Two-dimensional labyrinths are not a big challenge anymore. Thus, our labyrinth is d-dimensional. It looks like a regular ”grid” of n1×n2×. . .×nd (hyper)cubes, each of them being either empty (corridor) or filled with a rock (wall). Theseus moves in steps, each step means travelling between two neighboring empty hypercubes in any dimension. Two hypercubes are considered neighboring, if and only if the difference in their
space coordinates is exactly one in one dimension, and zero in all other dimensions.

2. Our Minotaur is stronger, thus, it is no more possible to batter him with bare hands. Theseus must use a sword which lies somewhere inside the labyrinth. Note that before he takes the sword, he cannot go through the hypercube where Minotaur resides!

输入:

Input Specification

The input consists of several labyrinth descriptions. Each description begins with a line containing a single integer number d (2 ≤ d ≤ 20) ― the number of dimensions. On the second line of each description, there are d integer numbers n1, n2, . . ., nd separated by spaces. These numbers give the size of the labyrinth in every dimension, measured in unit hypercubes (∀i : 2 ≤ ni). You may assume that the total number of hypercubes in any labyrinth will not exceed 220 = 1048576.

Then a labyrinth map follows, the description is defined recursively: Two-dimensional labyrinth (of the size n1 × n2) is described by n2 lines containing n1 characters each. Every character describes a single hypercube (”square” in the case of 2 dimensions) and is either “#” (rock), “.” (free space), or one of uppercase letters “T” (Theseus’ position), “M” (Minotaur), and ’S’ (sword). Each of these three objects will appear exactly once in the whole labyrinth. The hypercubes
containing the letters are considered ”empty” otherwise, i.e., Theseus can walk (and must walk) through them.

For better clarity of the input, each two-dimensional map is followed by one empty line.

For d > 2, any d-dimensional labyrinth is a sequence of nd ”layers”, each layer being a description of a (d − 1)-dimensional labyrinth.

The last labyrinth description is followed by a line containing zero. This line terminates the input and no output should be produced for it.

输出:

Input Specification

The input consists of several labyrinth descriptions. Each description begins with a line containing a single integer number d (2 ≤ d ≤ 20) ― the number of dimensions. On the second line of each description, there are d integer numbers n1, n2, . . ., nd separated by spaces. These numbers give the size of the labyrinth in every dimension, measured in unit hypercubes (∀i : 2 ≤ ni). You may assume that the total number of hypercubes in any labyrinth will not exceed 220 = 1048576.

Then a labyrinth map follows, the description is defined recursively: Two-dimensional labyrinth (of the size n1 × n2) is described by n2 lines containing n1 characters each. Every character describes a single hypercube (”square” in the case of 2 dimensions) and is either “#” (rock), “.” (free space), or one of uppercase letters “T” (Theseus’ position), “M” (Minotaur), and ’S’ (sword). Each of these three objects will appear exactly once in the whole labyrinth. The hypercubes
containing the letters are considered ”empty” otherwise, i.e., Theseus can walk (and must walk) through them.

For better clarity of the input, each two-dimensional map is followed by one empty line.

For d > 2, any d-dimensional labyrinth is a sequence of nd ”layers”, each layer being a description of a (d − 1)-dimensional labyrinth.

The last labyrinth description is followed by a line containing zero. This line terminates the input and no output should be produced for it.

样例输入:

2
3 3
T..
M#.
S..

2
3 2
T#S
..M

3
4 4 3
#S..
###.
#M..
###.

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

....
###.
###T
####

0

样例输出:

Theseus needs 8 steps.
No solution. Poor Theseus!
Theseus needs 40 steps.


(hplonline)2009.3.25题目应该说是意思很明了。就是走一个高维的迷宫。走二维的迷宫是此类问题中最直接接触的。一般的BFS可以很轻松的搞定。我们用dx[4] ={…},dy[4] = {…}这样的东西来记录一个增量。对当前点依次按照各个增量来走。判断新产生的点是否在地图外面,等等。当遇到三维的时候,我们习惯性地移植这种方法。加一个dz[4]就可以搞定了。有一个事实:每增加一个维度,可以走的方向增加两个。但是,当真正的多维迷宫出现的时候。上面的方法显然没法实现。就好比,你可以a = 1 , a = 1 + 2 , a = 1 + 2 + 3 但是a = 1 + 2 + … + 100 写起来就很臃肿了。对于一个n维迷宫,不至于写n个dXX[]来记录增量嘛。。所以,比较简洁的做法就是降维。这个东西听起来很像个意思。写起来还是比较囧的一个事情。一。思路描述d,总共的维度数目space[i]记录的是迷宫中第i个位置的情况。迷宫按照第一个维度,第二个维度。。。这样排成一行,就降成一维了。n[i]为第i个维度的长度,i = 0..dmv[i]是一个移动矢量,表示在第i个维度上移动一个单位,在space中实际上产生的距离那么mv[0] = 1 ;mv[i] = mv[i-1] * n[i-1] ;其中mv[d]表达的就是这个图中总共的点数。所以,当BFS的时候,对当前点curp依次加减每个维度上的增量。就可以得到新点的位置了。基本问题是解决了。但是还有一个更重要的问题:就是关于新点有效性的判定。在做二维的时候,习惯上是生成nx,ny然后看if ( nx >= 0 && nx < sx && ny >= 0 && ny < sy ){…}sx和sy是x和y维度的大小。那么,到n维的时候,这样就不行了。举个例子:有3*3的矩阵。排成0..8。当前点是2(即第0行的第2列)。如果现在先按照维度移动。可以得到点3(即第1行的第0列)。3点显然是在我们空间里面的,但这个移动又显然是不成立的。所以,要在移动之前判断。而这个判断说起来就比较绕口了。(感觉属于挑战表达能力的极限,那么我开始了。。)假设我们要在第i个维度上移动。我们就把前面的所有维度压缩成一个点。在i个维度上的移动一次的距离是mv[i],这个已经求得。那么在移动之前我们要检查:1.如果该点在于第k个i+1维度上,离第k个i+1维度的第一个i维度的距离是0,则不能进行减mv[i]的操作。2.如果该点在于第k个i+1维度上,离第k个i+1维度的第一个i维度的距离是n[i] – 1 , 则不能进行加mv[i]的操作。拿第一个说一下:curp / mv[i] 可以得到curp是总共的第几个i维度那么再 % n[i] 就算出离第k个i+1维度的第一个i维度的距离跟着判断就行了。关键的代码就是:           if ( ( curp / mv[i] ) % n[i] != n[i] – 1 ){                newp = curp + mv[i] ;                visit(newp);            }            if ( ( curp / mv[i] ) % n[i] != 0 ){                newp = curp – mv[i] ;                visit(newp);            }二。代码#include <stdio.h>#include <string.h>const int MAXCUBE = 1048576 ;int d ;int n[21] ;int mv[21] ;char space[MAXCUBE] ;int q[MAXCUBE] ;//队列int stp[MAXCUBE] ;//到达space[i]的步数int front , rear ;bool vst[MAXCUBE] ;//判重int p ;int s , m , t , curs;void visit(int pt){    if ( !(pt >= 0 && pt < mv[d]) ) {        return ;    }    if ( vst[pt] || space[pt] ) return ;    vst[pt] = true ;    stp[pt] = curs ;    q[rear] = pt ;    rear ++ ;}int bfs(int from , int to ){    int curp , newp ;    int i ;    memset(vst , false , sizeof(vst)) ;    front = 0 ;    rear = 1 ;    q[0] = from ;    stp[from] = 0 ;    vst[from] = true ;    while ( front < rear ){        curp = q[front ++] ;        curs = stp[curp] + 1;        if ( curp == to ) {            front — ;            break ;        }        for ( i = 0 ; i < d ; i ++ ){            if ( ( ( curp ) / mv[i] ) % n[i] != n[i] – 1 ){                newp = curp + mv[i] ;                visit(newp);            }            if ( ( ( curp ) / mv[i] ) % n[i] != 0 ){                newp = curp – mv[i] ;                visit(newp);            }        }    }    if ( front == rear ) return – 1;    else return stp[curp] ;}char nextchar(){    char ch ;    do{        ch = getchar() ;    }while ( ch != ‘#’ && ch != ‘.’ && ch != ‘S’ && ch != ‘M’ && ch != ‘T’ ) ;    if ( ch == ‘S’ ) s = p ;    if ( ch == ‘M’ ) m = p ;    if ( ch == ‘T’ ) t = p ;    if ( ch == ‘#’ ) return 1 ;    else return 0 ;}void readmap(int layer){    int i;    if ( layer == 0 ){        space[p ++ ] = nextchar() ;        return ;    }    for ( i = 0 ; i < n[layer - 1] ; i ++ ) readmap( layer – 1 ) ;}int main(){    int i ;    int ans ;    while (1){        scanf("%d",&d);        if ( d == 0 ) break ;        for ( i = 0 ; i < d ; i ++ ){            scanf("%d",n + i ) ;                    }        mv[0] = 1 ;        for ( i = 1 ; i <= d ; i ++ ){            mv[i] = n[i - 1] * mv[i - 1] ;        }        p = 0 ;        readmap(d) ;        ans = 0 ;        space[m] = 1 ;        i = bfs(t,s) ;        if ( i == -1 ){            ans = -1 ;        }else{            space[m] = 0 ;            ans += i ;            i = bfs(s,m) ;            if ( i == -1 ){                ans = -1 ;            }else{                ans += i ;                i = bfs(m,t) ;                if ( i == -1 ){                    ans = -1 ;                }else{                    ans += i ;                }            }        }        if ( ans == -1 )puts("No solution. Poor Theseus!");        else{            printf("Theseus needs %d steps.\n",ans);        }    }        return 0 ;}三。后话这东西在POJ上用G++交不过。。于是很郁闷地去搜了数据。拿下来发现是对的。。无解中。。。于是换C++ 交。。。然后就过了。。不知道谁看出是哪的问题了。。求解。
解题参考:http://hplonline20100103.blog.163.com/blog/static/1361364342010040027388/