admin 管理员组

文章数量: 887007

codevs 2855 游乐园的迷宫 bfs

题目描述  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

较长：

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

 

 

转载于:.html

本文标签： codevs2855 游乐园的迷宫 bfs

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