2855 游乐园的迷宫

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

迷宫可是每个游乐园必不可少的项目，菜菜当然是要尝试一下啦。

这个迷宫比较特殊。与其说是迷宫，倒不如说是一个巨大的格子。游乐园给菜菜发了一张地图，地图上标明了，这个格子由n行m列共n*m个小格子组成。有的格子可以正常走，标为’.’；有的格子有陷阱不能走，标为‘#’；有的格子比较特殊，标为‘*’，可以向周围八个方向可走的格子走一格；目的地标记为‘@’。菜菜从左上角处开始，并且可以按中国象棋中的马和象的方式或者特殊格的八方向来走。如果按照最短的路径到达目的地，则可以获得奖励。

菜菜当然想获得奖励啦，于是就来找你帮忙，请你帮忙计算最少需要多少步。

输入描述 Input Description

第一行，两个正整数n，m。

接下来的n行m列描述了地图。

输出描述 Output Description

一个整数，表示所要走的最小步数。若无法到达目的地则输出-1。

样例输入 Sample Input

11 10

..........

....#.....

..........

...#.*....

.......*..

..#..#...@

*.........

...#...#..

.....*....

...#......

..*....*..

样例输出 Sample Output

5 （题目样例有问题）

数据范围及提示 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 }