admin 管理员组文章数量: 887017
2855 游乐园的迷宫
2855 游乐园的迷宫
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description
迷宫可是每个游乐园必不可少的项目，菜菜当然是要尝试一下啦。
这个迷宫比较特殊。与其说是迷宫，倒不如说是一个巨大的格子。游乐园给菜菜发了一张地图，地图上标明了，这个格子由n行m列共n*m个小格子组成。有的格子可以正常走，标为’.’；有的格子有陷阱不能走，标为‘#’；有的格子比较特殊，标为‘*’，可以向周围八个方向可走的格子走一格；目的地标记为‘@’。菜菜从左上角处开始，并且可以按中国象棋中的马和象的方式或者特殊格的八方向来走。如果按照最短的路径到达目的地，则可以获得奖励。
菜菜当然想获得奖励啦，于是就来找你帮忙，请你帮忙计算最少需要多少步。
输入描述 Input Description第一行，两个正整数n，m。
接下来的n行m列描述了地图。
输出描述 Output Description一个整数，表示所要走的最小步数。若无法到达目的地则输出-1。
样例输入 Sample Input11 10
..........
....#.....
..........
...#.*....
.......*..
..#..#...@
*.........
...#...#..
.....*....
...#......
..*....*..
样例输出 Sample Output5 （题目样例有问题）
数据范围及提示 Data Size & Hint对于20%的数据，保证0＜n,m≤20
对于100%的数据，保证0＜n,m≤200
分析：首先一定要读题，读懂题（语文不好，啥也白搭），原以为你每个点可以跳马跳象，然后一般的还可以上下左右，*还点则八方位走，所以80！！！总是有答案。
第二遍以为只有一般的点可以跳马跳象，*点只能八方位走，最后我终于明白，所有的点都可以跳马跳象，而*点还能八方位走。orz
bfs搜索
1 #include<cstdio>
2 #include<queue>
3 #include<iostream>
4 using namespace std;
5
6 const int MAXN = 210;
7 struct node{
8 int x,y,step;
9 }cur,nxt;
10 char mp[MAXN][MAXN];
11 int bx[8] = {-1,-1,-1,0,0,1,1,1},by[8] = {-1,0,1,-1,1,-1,0,1};
12 int dx[12] = {1,1,2,2,-1,-1,-2,-2,2,2,-2,-2},dy[12] = {2,-2,1,-1,2,-2,1,-1,-2,2,-2,2};
13 bool v[MAXN][MAXN];
14 int n,m;
15 queue<node>q;
16
17 void bfs()
18 {
19 cur.x = 1;cur.y = 1;cur.step = 0;
20 q.push(cur);
21 v[1][1] = true;
22 if (mp[1][1]=='@')
23 {
24 printf("0");
25 return ;
26 }
27 while (!q.empty())
28 {
29 cur = q.front();
30 q.pop();
31 for (int i=0; i<12; ++i)
32 {
33 int xx = dx[i]+cur.x,yy = dy[i]+cur.y;
34 if (xx>0&&yy>0&&xx<=n&&yy<=m&&!v[xx][yy]&&mp[xx][yy]!='#')
35 {
36 if (mp[xx][yy]=='@')
37 {
38 printf("%d ",cur.step+1);
39 return ;
40 }
41 nxt.x = xx;nxt.y = yy;nxt.step = cur.step+1;
42 v[xx][yy] = true;
43 q.push(nxt);
44 }
45 }
46 if (mp[cur.x][cur.y]=='*')
47 for (int i=0; i<8; ++i)
48 {
49 int xx = bx[i]+cur.x,yy = by[i]+cur.y;
50 if (xx>0&&yy>0&&xx<=n&&yy<=m&&!v[xx][yy]&&mp[xx][yy]!='#')
51 {
52 if (mp[xx][yy]=='@')
53 {
54 printf("%d ",cur.step+1);
55 return ;
56 }
57 nxt.x = xx;nxt.y = yy;nxt.step = cur.step+1;
58 v[xx][yy] = true;
59 q.push(nxt);
60 }
61 }
62 }
63 printf("-1");
64 }
65 int main()
66 {
67 scanf("%d%d",&n,&m);
68 for (int i=1; i<=n; ++i)
69 for (int j=1; j<=m; ++j)
70 cin>>mp[i][j];
71 bfs();
72 return 0;
73 }
转载于:.html
本文标签： 2855 游乐园的迷宫
版权声明：本文标题：2855 游乐园的迷宫 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732360508h1535081.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论