Codevs 2855 游乐园的迷宫

2023-11-11 23:20
文章标签 codevs 迷宫 游乐园 2855

本文主要是介绍Codevs 2855 游乐园的迷宫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

　　　　　　　　　　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

13

数据范围及提示 Data Size & Hint

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

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

50分代码存档：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<queue>
 5 using namespace std;
 6 #define maxn 205
 7 int n,m,dis[maxn][maxn],ex,ey;
 8 int dx[]={-2,-2,-2,-2,-1,-1,+1,+1,+2,+2,+2,+2};
 9 int dy[]={-2,-1,+1,-2,+2,+2,-2,+2,-2,-1,+1,+2};
10 int bax[]={-1,-1,-1,0,0,1,1,1};
11 int bay[]={-1,0,1,-1,1,-1,0,1};
12 char map[maxn][maxn];
13 queue<int> stx,sty;
14 bool vis[maxn][maxn];
15 bool Judge(int xx,int yy){
16     if(xx>0&&xx<=n&&yy>0&&yy<=m&&map[xx][yy]!='#'&&!vis[xx][yy])
17       return true;
18     else return false;
19 }
20 void BFS(){
21     stx.push(1);sty.push(1);
22     while(!stx.empty()){
23         int nx=stx.front(),ny=sty.front();
24         stx.pop();sty.pop();
25         if(map[nx][ny]=='.'){
26             for(int i=0;i<12;i++){
27                 int xx=nx+dx[i],yy=ny+dy[i];
28                 if(Judge(xx,yy)){
29                     stx.push(xx);sty.push(yy);vis[xx][yy]=true;
30                     dis[xx][yy]=min(dis[xx][yy],dis[nx][ny]+1);
31                     if(xx==ex&&yy==ey) return;
32                 }
33             }
34         }
35         else if(map[nx][ny]=='*'){
36             for(int i=0;i<8;i++){
37                 int xx=nx+dx[i],yy=ny+dy[i];
38                 if(Judge(xx,yy)){
39                     stx.push(xx);sty.push(yy);vis[xx][yy]=true;
40                     dis[xx][yy]=min(dis[xx][yy],dis[nx][ny]+1);
41                     if(xx==ex&&yy==ey) return;
42                 }
43             }
44         }
45     }
46 }
47 int main()
48 {
49     memset(dis,0x3f,sizeof(dis));
50     scanf("%d%d",&n,&m);
51     for(int i=1;i<=n;i++)
52       for(int j=1;j<=m;j++){
53         cin>>map[i][j];
54         if(map[i][j]=='@') ex=i,ey=j;    
55       }
56     dis[1][1]=0;
57     BFS();
58     if(dis[ex][ey]==0x3f) printf("-1\n");
59     else printf("%d\n",dis[ex][ey]);
60     return 0;
61 }

AC代码：

 1 #include<iostream>
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 const int maxN  = 205;
 5 char maze[maxN][maxN];
 6 int n,m;
 7 int dx,dy;
 8 bool vis[maxN][maxN];
 9 struct Node {
10     int x,y;
11     int dep;//记录步数
12 };
13 bool is_raw(int x,int y) {
14     if(x >= 1 && x <= n && y >= 1 && y <= m && maze[x][y] != '#') return true;
15     return false;
16 }
17 bool ok = false;
18 int dir[24]= {1,2,1,-2, -1,2,-1,-2,  2,1,2,-1,  -2,-1,-2,1, //马
19               2,-2,-2,2,-2,-2,2,2};//象
20 int spec[16] = {-1,0,-1,-1,-1,1,   1,-1,1,1,1,0,  0,1,0,-1};//九宫格
21 int ans = 0;
22 void bfs() { //找最小，宽搜罗~
23     Node start;
24     start.x = 1, start.y = 1;
25     start.dep = 0;
26     queue<Node> q;
27     q.push(start);
28     while(!q.empty()) {
29         Node head = q.front();
30         //printf("x is %d, y is %d , dep is %d \n",head.x,head.y,head.dep);
31         if(head.x == dx && head.y == dy) {
32             ok = true;
33             ans = head.dep;
34             return;
35         }
36         q.pop();
37         for(int i = 0 ; i < 24; i = i + 2) {
38             if(is_raw(head.x+dir[i],head.y+dir[i+1])&&
39                     !vis[head.x+dir[i]][head.y+dir[i+1]]) {
40                 Node one;
41                 vis[head.x+dir[i]][head.y+dir[i+1]] = true;
42                 one.x = head.x+dir[i];
43                 one.y = head.y+dir[i+1];
44                 one.dep = head.dep+1;
45                 q.push(one);
46             }
47         }
48         if(maze[head.x][head.y] == '*') {
49             for(int i = 0 ; i < 16; i = i + 2) {
50                 if(is_raw(head.x+spec[i],head.y+spec[i+1])&&
51                         !vis[head.x+spec[i]][head.y+spec[i+1]]) {
52                     Node one;
53                     vis[head.x+spec[i]][head.y+spec[i+1]] = true;
54                     one.x = head.x+spec[i];
55                     one.y = head.y+spec[i+1];
56                     one.dep = head.dep+1;
57                     q.push(one);
58                 }
59             }
60         }
61     }
62 }
63 int main() {
64     cin>>n>>m;
65     memset(vis,0,sizeof(vis));
66     for(int i = 1 ; i <= n ; i++) {
67         for(int j = 1 ; j <= m; j++) {
68             cin>>maze[i][j];
69             if(maze[i][j] == '@')
70                 dx = i,dy = j;
71         }
72     }
73     //printf("目标是 %d %d\n",dx,dy);
74     bfs();
75     if(ok) printf("%d\n",ans);
76     else cout<<"-1"<<endl;
77 }

 //话说这题样例有问题，被样例坑了好长时间.......

再次AC代码：

 

/*
再次AC代码。。我日，我说咋回事吗，我感觉我写的也没什么
毛病就是不对挨！原来是题意理解错误 对于那些特殊的点既能够
按照八方向来走 ，也能够按照 普通点的 方向来走，刚开始写的时候
把两类点分开 写的。。。  
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define maxn 205
int n,m,dis[maxn][maxn],ex,ey;
int dx[]={-2,-2,-2,-2,-1,-1,+1,+1,+2,+2,+2,+2};
int dy[]={-2,-1,+1,-2,+2,+2,-2,+2,-2,-1,+1,+2};
int bax[]={-1,-1,-1,0,0,1,1,1};
int bay[]={-1,0,1,-1,1,-1,0,1};
char map[maxn][maxn];
queue<int> stx,sty;
bool vis[maxn][maxn];
bool Judge(int xx,int yy){
if(xx>0&&xx<=n&&yy>0&&yy<=m&&map[xx][yy]!='#'&&!vis[xx][yy])
return true;
else return false;
}
void BFS(){
stx.push(1);sty.push(1);
while(!stx.empty()){
int nx=stx.front(),ny=sty.front();
stx.pop();sty.pop();
for(int i=0;i<12;i++){
int xx=nx+dx[i],yy=ny+dy[i];
if(Judge(xx,yy)){
stx.push(xx);sty.push(yy);vis[xx][yy]=true;
dis[xx][yy]=min(dis[xx][yy],dis[nx][ny]+1);
if(xx==ex&&yy==ey) return;
}
}
if(map[nx][ny]=='*'){
for(int i=0;i<8;i++){
int xx=nx+dx[i],yy=ny+dy[i];
if(Judge(xx,yy)){
stx.push(xx);sty.push(yy);vis[xx][yy]=true;
dis[xx][yy]=min(dis[xx][yy],dis[nx][ny]+1);
if(xx==ex&&yy==ey) return;
}
}
}
}
}
int main()
{
memset(dis,0x3f,sizeof(dis));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>map[i][j];
if(map[i][j]=='@') ex=i,ey=j;    
}
dis[1][1]=0;
BFS();
if(dis[ex][ey]>=1500000) printf("-1\n");
else printf("%d\n",dis[ex][ey]);
return 0;
}

 

　　

 

这篇关于Codevs 2855 游乐园的迷宫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/393482。

相关文章

nyoj306(走迷宫)

nyoj306(走迷宫)

走迷宫 时间限制： 1000 ms  |  内存限制： 65535 KB 难度：5 描述 Dr.Kong设计的机器人卡多非常爱玩，它常常偷偷跑出实验室，在某个游乐场玩之不疲。这天卡多又跑出来了，在SJTL游乐场玩个不停，坐完碰碰车，又玩滑滑梯，这时卡多又走入一个迷宫。整个迷宫是用一个N * N的方阵给出，方阵中单元格中填充了一个整数，表示走到这个位置的难度。 这个迷宫可以向上走，向
阅读更多...
《GOF设计模式》—抽象工厂(Abstract Factory)—Delphi源码示例：基于抽象工厂的迷宫

《GOF设计模式》—抽象工厂(Abstract Factory)—Delphi源码示例：基于抽象工厂的迷宫

 示例：基于抽象工厂的迷宫   实现：     如果TMaze.Create是传递一个对象当作参数来建立rooms、walls及doors；如此你可以以不同的参数来改变rooms、walls及doors的类。  请注意MazeFactory也就是工厂方法(Factory Method)的一个集合；这是最通常实现抽象工厂模式的方式。同时请注意MazeFactory不是一个抽象类
阅读更多...
走迷宫变体【拼多多1面0905】

走迷宫变体【拼多多1面0905】

题目大致描述: 有一个N*M的迷宫，主角被放在随机的位置上，给你一个函数，控制主角逃离迷宫。 可以使用的函数：int move(String direction) (//direction代表上下左右四个方向，分别是“U"、“D"、“L"、“R"//返回值有3种，包括-1、0、1；-1表示前面是陷阱或墙，主角不能往前走，会留在原地；0表示迷宫出口，恭喜成功逃离；1表示前面可以走，主角前进一格）
阅读更多...
FZU1205/SDUT1157_小鼠迷宫问题(DFS+BFS)

FZU1205/SDUT1157_小鼠迷宫问题(DFS+BFS)

解题报告 http://blog.csdn.net/juncoder/article/details/38146041 题目传送门 题意 求最短路和最短路的路数。 思路： BFS+DFS，先求出最短路。在DFS搜等于最短路的条数。 不加优化SDUTOJ过了，数据就是水。 确定了最短路的长度，加上奇偶剪枝FOJ也过了。 #include <queue>#include <c
阅读更多...
A*算法解决迷宫寻路问题

A*算法解决迷宫寻路问题

A*算法解决迷宫寻路问题 问题描述 下图是一个迷宫，试为机器人找一条从Start到End的最短路径设计一搜索算法 设计思路 a)状态空间的表示 首先将迷宫图转换为列表形式呈现，每个格子用 （横坐标，纵坐标，上通路状态，下通路状态，左通路状态，右通路状态）来表示，通路状态用1或0表示，可通过为1，不可通过为0。比如起点（1，1），假定不能从起点出去，所以（1,1）可以走下或走右，所以第一格
阅读更多...
两种迷宫生成算法

两种迷宫生成算法

这里要介绍两种迷宫生成的算法，Recursive Backtracking和Eller’s Algorithm。它们都生成的是Perfect maze，也就是说每个区域都连通，并且没有环的迷宫。 我们现在说Recursive backtracking： 迷宫的初始状态是墙壁都存在。选择一个开始区域。 随机得选择一个没有访问过的邻接区域，并打通与它之间的墙壁。此邻接区域称为当前区域。
阅读更多...
深度优先遍历之迷宫生成算法

深度优先遍历之迷宫生成算法

1、图的深度优先遍历简介     例如，要遍历上面这个图  采取深度优先算法(从1开始)  准备一个Stack s，预定义三种状态：A未被访问 B正准备访问 C已经访问  一、访问1，把它标记为已经访问，然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问  此时系统状态：  已经被访问的点：1  还没有被访问的点：3 4
阅读更多...
HDU1269 迷宫城堡 （强连通图判定）

HDU1269 迷宫城堡 （强连通图判定）

题意：判定给出的有向图是不是强连通图 Tarjan算法模板题目 #include<cstdio>#include<iostream>#include<algorithm>#include<cmath>#include<set>#include<map>#include<string>#include<cstring>#include<stack>#include<queue
阅读更多...
【并查集】 HDU 1272 小希的迷宫

【并查集】 HDU 1272 小希的迷宫

HDU 1272 小希的迷宫 需要判断是否是连通图。 #include <iostream>#include <string>#include <algorithm>#include <math.h>#include <stdio.h>#include <cstring>#include <stdlib.h>using namespace std;int father[100
阅读更多...
[BFS广度优先搜索] 迷宫

[BFS广度优先搜索] 迷宫

描述 给定一个仅由数字 0 与 1 组成的 n 行 m 列的迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的任意一格 1 上；同样地，若你位于一格 1 上, 那么你可以移动到相邻 4 格中的任意一格 0 上。 现在，有 q 次询问。每次询问从给定的某一格 (第 x 行，第 y 列，均从 0 开始标号) 开始，在规则内任意移动。这样，有一些格子是可能到达的，而其余格子是无法到达的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2