Applese 走迷宫

2024-06-17 21:38
文章标签 迷宫 applese

本文主要是介绍Applese 走迷宫,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【题目描述】

精通程序设计的 Applese 双写了一个游戏。

在这个游戏中,它被困在了一个 n×m 的迷宫中,它想要逃出这个迷宫。

在迷宫中,有一些方格是水池,只有当 Applese 处于水属性的时候才可以通过;有一些方格是岩浆,只有当 Applese 是火属性的时候可以通过;有一些方格是墙壁,无论如何都无法通过;另一些格子是空地(包括起点和终点),可以自由通过。

在一些空地上有神秘道具可以让 Applese 转换自己的属性(从水属性变为火属性或从火属性变为水属性,需要一个单位的时间)。

已知 Applese 在一个单位的时间内可以朝四个方向行走一格,且开始处于水属性,位于空地的道具拾取后只能在该处立即使用(或者不使用),且可以多次使用。求它走出迷宫需要的最少时间。

【输入描述】

第一行两个正整数 n, m 表示迷宫的大小。
接下来 n 行,每行长度为 m 的字符串。描述地图。
其中 'S' 表示起点,'T' 表示终点,'.' 表示空地,'w'表示岩浆,'~'表示水池,'@' 表示道具,'#'表示障碍。
保证地图中的起点和终点只有一个,道具都位于空地。

1≤n,m≤100

【输出描述】

输出一个整数,表示 Applese 走出迷宫的最短时间。特别地,如果 Applese 走不出迷宫,输出 "-1"。

【样例】

示例1

输入
5 5
.w@..
.S#..
~w#..
.w..~
@w.~T
输出
18

思路:用 bfs 进行搜索求最短路,由于涉及到水火属性的问题,因此状态需要到达三维,即 dis[i][j][0/1] 表示在 (i,j) 处属性为水/火的最短路,然后按题意进行模拟,分类讨论转移

【源代码】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define PI acos(-1.0)
#define E 1e-6
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define N 101
#define LL long long
using namespace std;
char G[N][N];
bool vis[N][N][2];
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
struct Node{int x,y;//坐标int step;//步数bool sta;//水火的状态,0表示水,1表示火Node(){}Node(int x,int y,int step,bool sta):x(x),y(y),step(step),sta(sta){}
}S,T;
bool judge(int x,int y,bool sta){//检测当前属性能否通过if(G[x][y]=='w'&&!sta)return false;else if(G[x][y]=='~'&&sta)return false;return true;
}
int bfs(int n,int m){memset(vis,0,sizeof(vis));vis[S.x][S.y][0]=1;queue<Node> Q;Q.push(S);while(!Q.empty()){Node temp=Q.front();Q.pop();int x=temp.x;int y=temp.y;int step=temp.step;bool sta=temp.sta;if(x==T.x&&y==T.y)//到达终点return step;if(G[x][y]=='@'&&vis[x][y][!sta]==0){//属性变更Q.push( Node(x,y,step+1,!sta) );vis[x][y][!sta]=1;}for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx>=0&&ny>=0&&nx<n&&ny<m&&G[x][y]!='#'){if(judge(nx,ny,sta)){//检查当前属性能否通过当前格Node next=Node(nx,ny,step+1,sta);if(vis[nx][ny][sta]==0){Q.push(next);vis[nx][ny][sta]=1;}}}}}return -1;
}int main(){int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%s", G[i]);for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(G[i][j]=='S'){S.x=i;S.y=j;S.step=0;S.sta=0;//初始处于水属性}if(G[i][j]=='T'){T.x=i;T.y=j;}}}printf("%d\n",bfs(n,m));return 0;
}

 

这篇关于Applese 走迷宫的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1070546

相关文章

nyoj306(走迷宫)

走迷宫 时间限制: 1000 ms  |  内存限制: 65535 KB 难度:5 描述 Dr.Kong设计的机器人卡多非常爱玩,它常常偷偷跑出实验室,在某个游乐场玩之不疲。这天卡多又跑出来了,在SJTL游乐场玩个不停,坐完碰碰车,又玩滑滑梯,这时卡多又走入一个迷宫。整个迷宫是用一个N * N的方阵给出,方阵中单元格中填充了一个整数,表示走到这个位置的难度。 这个迷宫可以向上走,向

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

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

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

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

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

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

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 迷宫城堡 (强连通图判定)

题意:判定给出的有向图是不是强连通图 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 小希的迷宫 需要判断是否是连通图。 #include <iostream>#include <string>#include <algorithm>#include <math.h>#include <stdio.h>#include <cstring>#include <stdlib.h>using namespace std;int father[100

[BFS广度优先搜索] 迷宫

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