专栏首页算法时空CODE: 游乐园的迷宫

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;
 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 风险度量

    题目 X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路,构成通信网。 两个空间站间可能直接通信,也可能通过其它空间站中转。

    小二哥
  • 蓝桥杯之移动距离

    移动距离 X星球居民小区的楼房全是一样的,并且按矩阵样式排列。其楼房的编号为1,2,3… 当排满一行时,从下一行相邻的楼往反方向排号。 比如:当小区...

    小二哥
  • CODE:拯救伟哥

    题目 题目描述 Description 有一天,炜哥和欧能干一起去大魔王家里做(dao)客(luan),不巧被魔王发现了。魔王将炜哥和欧能干抓走了,关在...

    小二哥
  • 模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板

    图论 最短路 SPFA 1 #include<cstdio> 2 #include<queue> 3 #include<cstring> 4 using...

    attack
  • P1801 黑匣子_NOI导刊2010提高(06)

    题目描述 Black Box是一种原始的数据库。它可以储存一个整数数组,还有一个特别的变量i。最开始的时候Black Box是空的.而i等于0。这个Black ...

    attack
  • Codeforces Round 767C 树形结构求子树和

    很容易发现每一颗子树的点权是固定的,因为总和固定,设每一部分的大小为W,那么我们就从下往上更新,遇到等于W的子树就sz重置成0.

    用户2965768
  • HDU 3450 Counting Sequences(线段树)

    Counting Sequences Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 3276...

    ShenduCC
  • P1186 玛丽卡

    题目描述 麦克找了个新女朋友,玛丽卡对他非常恼火并伺机报复。 因为她和他们不住在同一个城市,因此她开始准备她的长途旅行。 在这个国家中每两个城市之间最多只有一条...

    attack
  • [HNOI2005]狡猾的商人 差分约束+判环

    定的sum[u→v]=c 不仅需要满足sum[v]−sum[u−1]=c,还应该满足sum[u−1]−sum[v]=−c。

    用户2965768
  • BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

    Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

    attack

扫码关注云+社区

领取腾讯云代金券