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 }

 

*………

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

5

..*….*..

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

…#…#..

较长:

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size &
Hint

题目描述 Description

…..*….

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

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

 

……….

输入描述 Input Description

…….*..

……….

..#..#…@

对于20%的数据,保证0<n,m≤20

….#…..

…#……

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

…#.*….

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

输出描述 Output Description

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

11 10

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>

using namespace std;
const int N=210;
const int xmx[]={-1,-2,-2,-1,1,2,2,1,-2,-2,2,2};
const int xmy[]={-2,-1,1,2,2,1,-1,-2,-2,2,2,-2};
const int spx[]={0,-1,-1,-1,0,1,1,1};
const int spy[]={-1,-1,0,1,1,1,0,-1};

struct node{
    int x,y,step;
}now,nxt;

int a[N][N];
bool vis[N][N];
int n,m;
int endx,endy;
queue<node>q;
int aaa;

inline int read()
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}

inline void bfs(int startx,int starty)
{
    now.x=startx;
    now.y=starty;
    now.step=0;
    q.push(now);
    vis[now.x][now.y]=1;
    while(!q.empty())
    {

        now=q.front();
        q.pop();
        int x=now.x,y=now.y;
        if(a[x][y]==1)
        {
            for(int i=0;i<12;i++)
            {
                int xx=x+xmx[i],yy=y+xmy[i];
                if(!vis[xx][yy]&&a[xx][yy]&&xx>0&&xx<=n&&yy>0&&yy<=m)
                {
                    nxt.x=xx;
                    nxt.y=yy;
                    nxt.step=now.step+1;
                    vis[xx][yy]=1;
                    if(xx==endx&&yy==endy)
                    {
                        printf("%d",nxt.step);
                        exit(0);
                    }
                    q.push(nxt);
                    aaa=q.size();
                }
            }
        }
        else if(a[x][y]==2)
        {
            for(int i=0;i<8;i++)
            {
                int xx=x+spx[i],yy=y+spy[i];
                if(!vis[xx][yy]&&a[xx][yy]&&xx>0&&xx<=n&&yy>0&&yy<=m)
                {
                    nxt.x=xx;
                    nxt.y=yy;
                    nxt.step=now.step+1;
                    vis[xx][yy]=1;
                    if(xx==endx&&yy==endy)
                    {
                        printf("%d",nxt.step);
                        exit(0);
                    }
                    q.push(nxt);
                }
            }
        }
    }
}

int main()
{
    n=read();
    m=read();

    for(int i=1;i<=n;i++)
    {
        char c;
        for(int j=1;j<=m;j++)
        {
            vis[i][j]=0;
            scanf("%c",&c);
            if(c=='.')a[i][j]=1;
            if(c=='*')a[i][j]=2;
            if(c=='#')a[i][j]=0;
            if(c=='@')endx=i,endy=j,a[i][j]=1;
        }
        scanf("%c",&c);
    }
    bfs(1,1);
    printf("-1");
    return 0;
}

//kk:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
using namespace std;
const int go1[20][2]= {1,2,2,2,2,1,2,-1,2,-2,1,-2,-1,-2,-2,-2,-2,-1,-2,1,-2,2,-1,2,0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1,};
struct node {
    int x,y,w,step;
};
queue<node> q;
int map[210][210],mark[210][210],n,m;
char s[210];
int main() 
{
    int i,j,f=1,sx,sy,ex,ey;
    node t,tmp;
    scanf("%d%d",&n,&m);
    sx=sy=1;
    for(i=1; i<=n; i++) 
    {
        scanf("%s",s);
        for(j=1; j<=m; j++)
            if(s[j-1]=='#')map[i][j]=1;
            else if(s[j-1]=='*')map[i][j]=2;
        else if(s[j-1]=='@') 
        {
            ex=i;
            ey=j;
        }
            else map[i][j]=0;
    }
    t.x=sx;
    t.y=sy;
    t.w=map[1][1];
    t.step=0;
    q.push(t);
    mark[sx][sy]=1;
    while(!q.empty()) 
    {
        tmp=q.front();
        q.pop();
        if(tmp.x==ex&&tmp.y==ey) 
        {            
            printf("%d\n",tmp.step);
            f=0;
            break;
        }
        if(tmp.w==0) 
        {
            for(i=0; i<12; i++) 
            {
                t.x=tmp.x+go1[i][0];
                t.y=tmp.y+go1[i][1];
                t.step=tmp.step+1;
                if(t.x>=1&&t.x<n+1&&t.y>=1&&t.y<m+1&&!mark[t.x][t.y]&&map[t.x][t.y]!=1) 
                {
                    t.w=map[t.x][t.y];
                    mark[t.x][t.y]=t.step;
                    q.push(t);
                }
            }
        } else 
        {
            for(i=0; i<20; i++) 
            {
                t.x=tmp.x+go1[i][0];
                t.y=tmp.y+go1[i][1];
                t.step=tmp.step+1;
                if(t.x>=1&&t.x<n+1&&t.y>=1&&t.y<m+1&&!mark[t.x][t.y]&&map[t.x][t.y]!=1) 
                {
                    t.w=map[t.x][t.y];
                    mark[t.x][t.y]=t.step;
                    q.push(t);
                }
            }
        }
    }
    if(f)printf("-1\n");
    return 0;

}

 

admin

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注