admin 管理员组

文章数量: 887007

CODE： 游乐园的迷宫

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

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

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

输入描述 Input Description
第一行，两个正整数n，m。

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

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

样例输入 Sample Input
11 10

……….

….#…..

……….

…#.*….

…….*..

..#..#…@

*………

…#…#..

…..*….

…#……

..…...

样例输出 Sample Output
13

数据范围及提示 Data Size & Hint
对于20%的数据，保证0＜n,m≤20

对于100%的数据，保证0＜n,m≤200

代码

#include<iostream>
#include<queue>
using namespace std;const int maxn = 205;
int mp[maxn][maxn] = {0};
int vis[maxn][maxn] = {0};
int n,m;
struct Node{int x,y;int step;
};
int dir[12][2] = {{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{1,2},{-1,2},{-2,2},{2,2},{-2,-2},{2,-2}};
int spe[8][2] = {{-1,1},{-1,0},{-1,-1},{0,1},{0,-1},{1,1},{1,-1},{1,0}};
int jude = 0;
int operate(int &x,int &y,int step,int flag)
{if(flag){x+=dir[step][0];y+=dir[step][1];}else{x+=spe[step][0];y+=spe[step][1];}if(x<=0||x>n||y<=0||y>m||!mp[x][y]||vis[x][y]){return 0;}return 1;
}
void bfs()
{queue<Node> q;q.push((Node){1,1,0});  while(!q.empty()){Node n = q.front(); q.pop();int a,b;if(mp[n.x][n.y]==3){cout << n.step<<endl;jude = 1;return ;}for(int i = 0; i < 12; i++){a = n.x;b = n.y;if(!operate(a,b,i,1))continue;q.push((Node){a,b,n.step+1});vis[a][b] = 1;}a = n.x;b = n.y;if(mp[a][b]==2){for(int j = 0; j < 8; j++){if(!operate(a,b,j,1))continue;q.push((Node){a,b,n.step+1});vis[a][b] = 1;}}   }   return ;
}
int main()
{cin >> n >> m;for(int i =1; i <= n; i++){for(int j = 1; j<=m; j++){char temp;cin >> temp;if(temp=='#')mp[i][j] = 0;if(temp=='.')mp[i][j] = 1;if(temp=='*')mp[i][j] = 2;if(temp=='@')mp[i][j] = 3;}}bfs();if(!jude){cout << "-1" << endl;}return 0;}

本文标签： CODE 游乐园的迷宫

版权声明：本文标题：CODE： 游乐园的迷宫 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732360655h1535119.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。