BNU - 49102
进化之地(Evoland)
最近xhyu和hwq欢乐地通了一款RPG(Role-playing game)神作——《进化之地》,这是一部用RPG讲述RPG发展史的RPG。随 着剧情发展,游戏从最原始的2D黑白像素块无音乐模式,逐渐变为32位色图,有了音效,开启打怪、对话、升级模式,纹理映射,连NPC都是开宝箱开出来 的,带着玩家从20年前的FC时代走到如今的3D动作游戏中。
其中一个名为“神圣森林”的迷宫设计十分巧妙,玩家需要不停地在2D画面和3D画面之间切换来通过。
如下图:
很明显左边是2D模式,右边是3D 模式。
2D模式下,小树苗(左边红圈)可以通过,而高台(上方红圈)不能通过;
3D模式下,小树苗(中间红圈)不能通过,而高台(下方红圈)可以通过;
两个模式中,都有一个蓝色的东西,那是时空之石,通过击打它可以在2D模式与3D模式间转换。
经过半个小时努力终于通过这里以后,聪慧的hwq表示要用ACM的眼光严肃看待这个问题,于是随手画了几个图,让xhyu速速的找到每个图的解法,找不到没人权。
为了尽快恢复人权,xhyu只好向聪慧的你求助。
注意:为了避免误会说明一下,上面两幅图不是同一个小场景的截图,正常情况下,当击打时空之石时,场景中所有物品的相对位置不变,只是2D效果和3D效果改变了。
Input
输入的第一行是一个整数t,表示数据组数。(t<=30)
对每组数据:第一行三个整数n,m,分别为地图的行数、列数。(1<n,m<=100)
接下来有n行字符串,每行m个字符,各个字符含义:
0 起点(每图只有一个,初始为2D)
1 终点(每图只有一个,结束时可以是2D可以是3D)
. 通路(2D/3D均可通过)
# 障碍物(2D/3D均不可通过)
@ 时空之石(2D/3D均可通过)
2 小树苗(2D可通过,3D不可通过)
3 高台(3D可通过,2D不可通过)
保证每个图的时空之石数量不超过12,保证输入合法。
注意:
1.初始为2D状态,到达终点时可以2D也可以3D;
2.经过时空之石时可以选择切换2D/3D也可以不切换;
3.必须走到时空之石那一格才能切换2D/3D,时空之石可以正常通过;
4.切换2D/3D是在原地进行,不算做一步;
5.中途允许经过起点,时空之石可以多次使用,障碍物无论2D/3D都不能通过。
Output
每组数据输出一个整数,表示从起点走到终点最少需要多少步,如果不能走到终点,则输出-1。
Sample Input
3
1 6
#@0.31 1 7
2@303.1 7 5
.####
.1..#
###3#
.@#.#
.##.#
....#
0####
Sample Output
5
-1
16
Hint
各字符宽度不一样不方便查看,建议把样例写下来观察。
(1)先向左走到@转换为3D,再向右走到终点;
(2)初始是2D,左右都走不通,无解输出-1;
(3)先去触发时空之石,再去终点;
#include <iostream>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <vector>
#define maxn 110
using namespace std;
char ch[maxn][maxn];
int dx[] = {,,-,};
int dy[] = {,-,,};
int n,m;
int vis[][][];
struct Node
{
int x;
int y;
int step;
int dime;
} start,end;
int check(Node a) ///二维
{
if(a.x >= && a.x <n && a.y >= && a.y <m ) return ;
return ;
}
int bfs()
{
Node now,tmp,temp;
queue<Node>que;
vis[start.x][start.y][] = ;
while(!que.empty()) que.pop();
que.push(start);
while(!que.empty())
{
tmp = que.front();
que.pop();
for(int i=; i<; i++)
{
now.x = tmp.x + dx[i];
now.y = tmp.y + dy[i];
now.step = tmp.step + ;
if(ch[now.x][now.y] == '')
{
return now.step;
}
if(check(now))
{
if(ch[now.x][now.y] == '.' )
{
now.dime= tmp.dime ;
if(!vis[now.x] [now.y][now.dime])
{
que.push(now);
vis[now.x] [now.y][now.dime] = ;
} }
else if(ch[now.x][now.y] == '')
{
if(tmp.dime == )
{
now.dime = ;
if(!vis[now.x] [now.y][now.dime])
{
que.push(now);
vis[now.x] [now.y][now.dime] = ;
}
}
}
else if(ch[now.x][now.y] == '')
{
if(tmp.dime == )
{
now.dime = ;
if(!vis[now.x] [now.y][now.dime])
{
que.push(now);
vis[now.x] [now.y][now.dime] = ;
}
}
}
else if(ch[now.x][now.y] == '@')
{
now.dime = ;
if(!vis[now.x] [now.y][now.dime])
{
que.push(now);
vis[now.x] [now.y][now.dime] = ;
}
now.dime = ;
if(!vis[now.x] [now.y][now.dime])
{
que.push(now);
vis[now.x] [now.y][now.dime] = ;
}
}
}
}
}
return ;
}
int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
memset(vis,,sizeof(vis));
memset(ch,'\0',sizeof(ch));
scanf("%d %d",&n,&m);
for(int i=; i<n; i++)
{
scanf("%s",ch[i]);
for(int j=; j<m; j++)
{
if(ch[i][j] == '')
{
start.x = i;
start.y = j;
ch[i][j] = '.';
start.step = ;
start.dime = ;
}
if(ch[i][j] == '')
{
end.x = i;
end.y = j;
}
}
}
int res = -;
res = bfs();
if(res) printf("%d\n",res);
else printf("-1\n");
}
return ;
}
最新文章
- Node聊天程序实例05:index.html和style.css
- apache2服务器mod_rewrite模块 开启方法[linux, ubuntu]
- 20150624_Andriod _web_service_匹配
- jq实现多级手风琴效果
- PHP函数——parse_ini_file() 函数
- Lines演示程序
- ASP.NET MVC- VIEW Overview Part 1
- MVC第一节 配置
- centos php 扩展安装
- VS下载地址
- Spring+SpringMVC+MyBatis深入学习及搭建(三)——MyBatis全局配置文件解析
- 2017-06-19 (cp mkdir rm 运行级别及修改)
- 我带着小程序和Springboot后端终于战胜了WebSocket!!!胜利( •̀ ω •́ )y
- Java开发笔记(七)强制类型转换的风险
- python MRO:C3算法
- iTools(pro)下载
- Linux DMA Engine framework(3)_dma controller驱动
- 张钹院士:场景是当前AI产业化最大问题
- PHP获取文件后缀名
- Bluedroid: 蓝牙协议栈源码剖析