# HDU 1448 The Treasure-BFS-[解题报告] C++

2016-03-12 10:21:54来源:[db:出处]作者:[db:作者]人点击

The Treasure

We have arrived at the age of the Internet. Many software applications have transformed from stand-alone to online applications. Computer games are following this trend as well. Online games are becoming more and more popular, not only because they are more intelligent, but also because they can bring great profits. "The computer game industry is developing rapidly in China. Online game revenues amounted to 1.3 billion Yuan last year and are expected to reach 6.7 billion Yuan by 2007." reported by China Daily in 2004.

However, good games originate from good programmers. We take for example that there is a RPG (Role Playing Game) and your boss asks you to implement some tasks. For simplicity’s sake, we assume there are two kinds of roles in this game: one is player and the other is monster. You should help the player to achieve the goal: reach the place where treasure is positioned as early as possible and get the treasure.

The map of the game is a matrix of N * M identical cells. Some cells are passable blocks, and others are non-passable rocks. At any time, there is at most one role occupying a block. At the beginning, the time is set to 0, and the player is at a certain block. He then moves towards the treasure. At each turn, we have some rules:

1) The player can stay in the same block during the next one-second time duration, or he can walk or run towards the east, south, west, north, northeast, northwest, southeast, and southwest.

2)%20With%20walking,%20the%20player%20can%20arrive%20at%20the%20corresponding%20passable%20blocks%20around%20him%20(See%20Fig.1).%20Each%20move%20takes%201%20second.%20

3)%20With%20running,%20the%20player%20can%20arrive%20at%20the%20corresponding%20passable%20blocks%202%20cells%20away%20from%20him%20(See%20Fig.2).%20Each%20run%20takes%201%20second.%20As%20demonstrated%20in%20Fig.3,%20if%20a%20neighbor%20cell%20is%20not%20passable,%20the%20player%20cannot%20run%20in%20that%20direction.%20For%20example,%20if%20cell%202%20is%20a%20rock,%20running%20from%201%20to%203%20is%20impossible.%20

%20输入:

The%20input%20consists%20of%20several%20test%20cases.%20The%20first%20line%20of%20each%20case%20contains%20two%20integers%20N%20and%20M%20(1%20<=%20N,%20M%20<=%20100),%20where%20N%20is%20the%20height%20of%20the%20map%20and%20M%20is%20the%20width%20of%20the%20map.%20This%20is%20followed%20by%20N%20lines%20each%20containing%20M%20characters%20representing%20the%20map.%20A%20‘#’%20represents%20a%20rock,%20a%20‘.’%20is%20a%20free%20block,%20‘p’%20is%20the%20starting%20position%20of%20the%20player,%20‘t’%20is%20the%20position%20of%20the%20treasure,%20‘n’%20is%20the%20initial%20position%20of%20a%20non-aggressive%20monster,%20and%20an%20‘a’%20stands%20for%20the%20initial%20position%20of%20an%20aggressive%20monster.%20

The%20cell%20(i,%20j)%20is%20the%20j-th%20cell%20on%20the%20i-th%20row%20counting%20from%20left%20to%20right.%20The%20rows%20are%20counted%20from%201%20to%20N%20starting%20from%20the%20first%20line%20of%20the%20matrix.%20We%20can%20number%20all%20the%20monsters%20as%201,%202,%203…%20according%20to%20their%20initial%20position,%20sorting%20first%20by%20row,%20then%20by%20column.%20The%20(n+2)-th%20line%20contains%20an%20integer%20p%20(0%20<=%20p%20<=%20100),%20which%20is%20the%20total%20number%20of%20monsters%20(i.e.%20the%20total%20number%20of%20‘n’s%20and%20‘a’s%20in%20the%20matrix).%20It%20is%20followed%20by%20p%20lines%20each%20specifying%20a%20monster’s%20position%20sequence%20in%20the%20following%20format:%20the%20i-th%20(1%20<=%20i%20<=%20p)%20line%20corresponds%20to%20monster%20i,%20which%20begins%20with%20an%20integer%20s%20(1%20<=%20s%20<=%20100),%20meaning%20the%20length%20of%20position%20sequence.%20Then%20s%20pairs%20of%20integers%20x1,%20y1,%20x2,%20y2,%20…,%20xs,%20ys%20are%20followed,%20separated%20by%20blanks.%20Each%20pair%20is%20a%20free%20block%20in%20the%20map,%20(i.e.%20a%20monster%20never%20goes%20to%20a%20rock%20cell).%20

It%20is%20assured%20that%20none%20of%20the%20aggressive%20monsters’%20initial%20position%20is%20around%20the%20player.%20Two%20consecutive%20cases%20are%20separated%20by%20a%20blank%20line.%20The%20input%20is%20terminated%20by%20a%20line%20containing%20a%20pair%20of%20zeros.%20%20

%20输出:

For%20each%20test%20case,%20output%20the%20minimum%20total%20time%20required%20for%20the%20player%20to%20get%20the%20treasure,%20in%20seconds.%20If%20it’s%20not%20possible%20to%20get%20the%20treasure,%20or%20the%20minimum%20required%20time%20is%20greater%20than%20100%20seconds,%20please%20print%20a%20line%20just%20containing%20the%20string"impossible". Two consecutive cases should be separated by a blank line.

7 8#.#####.#.t#..p.#..#......#a.#.##...##.n.#..............22 4 4 5 43 5 8 6 8 5 73 3p#.##.t..02 2#tp#00 0

8impossible1HintIn the first sample case, the player can follow (2,7), (4,7), stay in (4,7), (6,7), (7,6), (7,4), (5,2), (3,2) and (2,3) to get the treasure with the minimum time (8 seconds).

#include #include #include #include #include #include #include #include using namespace std;struct Point{ int x; int y; int z;};Point s,e;int map[35][35][35];int vis[35][35][35];int dist[35][35][35];int disx[6] = {-1,0,1,0,0,0};int disy[6] = {0,1,0,-1,0,0};int disz[6] = {0,0,0,0,1,-1};int l,r,c;int bfs(){ queue p; Point temp,nex; p.push(s); vis[s.x][s.y][s.z] = 1; while(!p.empty()) { temp = p.front(); p.pop(); for(int i=0; i<6; i++) { int tempx = temp.x + disx[i]; int tempy = temp.y + disy[i]; int tempz = temp.z + disz[i]; //注意我这里把x作为第一维，y作为第二维，z作为第三维 if(tempx>=1 && tempx<=l && tempy>=1 && tempy<=r && tempz>=1 && tempz<=c) { if(vis[tempx][tempy][tempz] == 0 && map[tempx][tempy][tempz] == 1) { vis[tempx][tempy][tempz] = 1; nex.x = tempx,nex.y = tempy,nex.z = tempz; dist[nex.x][nex.y][nex.z] = dist[temp.x][temp.y][temp.z] + 1; if(nex.x == e.x && nex.y == e.y && nex.z == e.z) { return dist[nex.x][nex.y][nex.z]; } p.push(nex); } } } } return 0;}int main(){#ifndef ONLINE_JUDGE freopen("in.txt","r",stdin);#endif char str[35]; while(scanf(" %d %d %d",&l,&r,&c)!=EOF && l!=0 && r!=0 && c!=0) { memset(vis,0,sizeof(vis)); memset(dist,0,sizeof(dist)); memset(map,0,sizeof(map)); for(int i = 1; i<=l; i++) { for(int j=1; j<=r; j++) { scanf(" %s",str); for(int k=0; k