文档章节

sicily 1215 脱离地牢

Ciel
 Ciel
发布于 2013/01/03 23:16
字数 1345
阅读 114
收藏 0

Description

在一个神秘的国度里,年轻的王子Paris与美丽的公主Helen在一起过着幸福的生活。他们都随身带有一块带磁性的阴阳魔法石,身居地狱的魔王Satan早就想得到这两块石头了,只要把它们熔化,Satan就能吸收其精华大增自己的魔力。于是有一天他趁二人不留意,把他们带到了自己的地牢,分别困在了不同的地方。然后Satan念起了咒语,准备炼狱,界时二人都将葬身于这地牢里。

危险!Paris与Helen都知道了Satan的意图,他们要怎样才能打败魔王,脱离地牢呢?Paris想起了父王临终前留给他的备忘本,原来他早已料到了Satan的野心,他告诉Paris只要把两块魔法石合在一起,念出咒语,它们便会放出无限的光亮,杀死魔王,脱离地牢,而且本子上还附下了地牢的地图,Paris从中了解到了Helen的位置所在。于是他决定首先要找到Helen,但是他发现这个地牢很奇怪,它会增强二人魔法石所带磁力的大小,而且会改变磁力的方向。这就是说,每当Pairs向南走一步,Helen有可能会被石头吸引向北走一步。而这个地狱布满了岩石与熔浆,Pairs必须十分小心,不仅他不能走到岩石或熔浆上,而且由于他行走一步,Helen的位置也会改变,如果Helen碰到岩石上,那么她将停留在原地,但如果Helen移动到了熔浆上,那么她将死去,Paris就找不到她了。

Pairs仔细分析了地图,他找出了一条最快的行走方案,最终与Helen相聚。他们一起念出了咒语"@^&#……%@%&$",轰隆一声,地牢塌陷了,他们又重见光明……

Input

输入数据第一行为两个整数n,m(3<=n,m<=20),表示地牢的大小,n行m列。接下来n行,每行m个字符,描述了地牢的地图,"."代表通路,"#"代表岩石,"!"代表熔浆。输入保证地牢是封闭的,即四周均是均是岩石或熔浆。接下来一行有四个字符"N"(北),"S"(南),"W"(西),"E"(东)的排列,表示Paris分别向NSWE四个方向走时Helen受磁石磁力影响的移动方向。

Output

输出文件只有一行,如果Paris能找到Helen,输出一整数d,为Paris最少需要行走的步数;如果Paris在255步之后仍找不到Helen,则输出"Impossible"。注意相遇是指Paris与Helen最终到达同一个格子,或者二人在相邻两格移动后碰在了一起,而后者的步数算他们移动后的步数。

Sample Input

5 5
#####
#H..#
#.!.#
#.#P#
#####
WNSE

Sample Output

5

解释:Paris行走方案为NNWWS,每步过后Helen位置在(2,2), (2,2), (3,2), (4,2), (3,2)。

分析:

本题是经典的迷宫问题,但是很特殊的是本题中有两个同时移动元素,而解决迷宫问题的广搜方法需要记录的是每一步的状态,所以本题的重点其实是在状态的明确上。本题看似可以用Paris一个人的状态来记录,但是其实会产生问题,如果Paris不访问他已经访问的点,会丢失部分状态,因为他访问同一个点并不代表Helen也会走同样的路线。所以,状态应该以两人的位置组合为标志,同时要注意状态的处理和判断,那么几点是否访问的记录数组应该是思维的。另外,注意两人可能相撞的情况只当两人相邻,并且各自走到对方的上一步节点才可能。

代码:

// Problem#: 1215
// Submission#: 1854023
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define MAX 20
int n, m;
 
struct state{
    int P_x, P_y, H_x, H_y;
    int step;
    bool same(){
        return P_x == H_x && P_y == H_y;
    }
    bool judge(){
        return P_x > 0 && P_x <= n &&  P_y > 0 && P_y <= m
        && H_x > 0 && H_x <= n && H_y > 0 && H_y <= m ;
    }
    bool ismeet(state s){
        return P_x == s.H_x && P_y == s.H_y && H_x == s.P_x && H_y == s.P_y;
    }
    state(int P_x, int P_y, int H_x, int H_y) {
        this->H_x = H_x; this->H_y = H_y; this->P_x = P_x; this->P_y = P_y; step = 0;
    }
    state() {
        step = 0;
    }
};
 
enum direction{N, S, W, E};
 
int move[4][2] = {{-1, 0},{1, 0}, {0, -1}, {0, 1}};
int match[4];
char _mape[MAX][MAX];
bool visit[MAX][MAX][MAX][MAX];
 
int P_x, P_y, H_x, H_y;
 
void bfs();
 
int main(){
    char c;
    while (cin >> n >> m){
        memset(visit, false, sizeof(visit));
 
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= m; j++){
                cin >> _mape[i][j];
                if (_mape[i][j] == 'P'){
                    P_x = i;
                    P_y = j;
                    _mape[i][j] = '.';
                }
                if (_mape[i][j] == 'H'){
                    H_x = i;
                    H_y = j;
                    _mape[i][j] = '.';
                }
            }
 
            for (int i = 0; i < 4; i++){
                cin >> c;
                switch (c){
                case 'N':
                    match[i] = N;
                    break;
                case 'S':
                    match[i] = S;
                    break;
                case 'W':
                    match[i] = W;
                    break;
                case 'E':
                    match[i] = E;
                    break;
                }
            }
            bfs();
    }
    return 0;
}
 
void bfs(){
    queue <state> buffer;
    buffer.push(state(P_x, P_y, H_x, H_y));
 
    state temp, next;
 
    while (!buffer.empty()){
        temp = buffer.front();
        buffer.pop();
        if (temp.step > 255){
            cout << "Impossible" << endl;
            return;
        }
        for (int i = 0; i < 4; i++){
            next.P_x = temp.P_x + move[i][0];
            next.P_y = temp.P_y + move[i][1];
            next.H_x = temp.H_x + move[match[i]][0];
            next.H_y = temp.H_y + move[match[i]][1];
            next.step = temp.step + 1;
         
            if (next.judge() && _mape[next.H_x][next.H_y] != '!' 
        && _mape[next.P_x][next.P_y] == '.' ){
                if (_mape[next.H_x][next.H_y] == '#'){
                    next.H_x -= move[match[i]][0];
                    next.H_y -= move[match[i]][1];
                }
                if (!visit[next.P_x][next.P_y][next.H_x][next.H_y]){
                    visit[next.P_x][next.P_y][next.H_x][next.H_y] = true;
                    if (next.same() || temp.ismeet(next)){
                        cout << next.step << endl;
                        return ;
                    }
                    else
                        buffer.push(next);
                }
            }
        }
 
    }
    cout << "Impossible" << endl;
}

© 著作权归作者所有

上一篇: sicily 1444 Prime Path
下一篇: sicily 1048 Inverso
Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
Oracle 11g R2 ADG 搭建

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v$database; 如果为noarchivelog模式,切换到archivelo......

UltraSQL
2018/07/23
0
0
POJ 2251 Dungeon Master

Dungeon Master   You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It tak......

suvvm
2018/12/06
0
0
nginx反向代理iis下的asp.net网站报错,急!!!!

想要做nginx和iis的负载均衡,但是反向代理无法正确跳转。iis下的网站能正常打开,反向代理无法正常打开。 http://site:1215/account/login?returnurl=%2f&RequestId=d66c1ab5 配置文件为: ...

思想犯罪_狼
2015/11/23
1K
2
codecombat之边远地区的森林23-30关及地牢40\41关代码分享

codecombat中国游戏网址:http://www.codecombat.cn/ 所有代码为javascript代码分享 23、Agrippa防守 loop { var enemy = this.findNearestEnemy(); if(enemy) { // 用 distanceTo 获取与敌人......

comA
2015/08/26
0
0
使用dispatch_once实现单例模式

单例模式是一种常用的软件设计模式。在它的核心结构中只包含一个被称为单例类的特殊类。通过单例模式可以保证系统中一个类只有一个实例而且该实例易于外界访问,从而方便对实例个数的控制并节...

c-ys
2015/12/09
24
0

没有更多内容

加载失败,请刷新页面

加载更多

iOS Xcode升级包地址(感谢大神)

下载地址:DeviceSupport

_____1____
10分钟前
4
0
Qt编写自定义控件71-圆弧进度条

一、前言 现在web形式的图表框架非常流行,国产代表就是echart,本人用过几次,三个字屌爆了来形容,非常强大,而且易用性也非常棒,还是开源免费的,使用起来不要太爽,内置的各种图表和仪表...

飞扬青云
10分钟前
3
0
润乾报表与 ActiveReport JS 功能对比

简介 润乾报表是用于报表制作的大型企业级报表软件,核心特点在于开创性地提出了非线性报表数学模型,采用了革命性的多源关联分片、不规则分组、自由格间运算、行列对称等技术,使得复杂报表...

泡泡糖儿
22分钟前
4
0
【1015】LNMP架构二

【1015】LNMP架构二 三、PHP安装 PHP安装和LAMP安装PHP方法有差别,需要开启php-fpm服务 1、下载PHP7至/usr/local/src/ 切换目录:cd /usr/local/src 2、解压缩 tar -jxvf php-7.3.0.tar.gz...

飞翔的竹蜻蜓
56分钟前
5
0
浅谈Visitor访问者模式

一、前言 什么叫访问,如果大家学过数据结构,对于这点就很清晰了,遍历就是访问的一般形式,单独读取一个元素进行相应的处理也叫作访问,读取到想要查看的内容+对其进行处理就叫作访问,那么...

青衣霓裳
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部