文档章节

sicily 1135 飞越原野

Ciel
 Ciel
发布于 2013/01/06 21:49
字数 1069
阅读 114
收藏 0

Description

勇敢的德鲁伊法里奥出色的完成了任务之后,正在迅速的向自己的基地撤退。但由于后面有着一大群追兵,所以法里奥要尽快地返回基地,否则就会被敌人捉住。

终于,法里奥来到了最后的一站:泰拉希尔原野,穿过这里就可以回到基地了。然而,敌人依然紧追不舍。不过,泰拉希尔的地理条件对法里奥十分有利,众多的湖泊随处分布。敌人需要绕道而行,但法里奥拥有变成鹰的特殊能力,使得他能轻轻松松的飞越湖面。当然,为了保证安全起见,法里奥还是决定找一条能最快回到基地的路。

假设泰拉希尔原野是一个m*n的矩阵,它有两种地形,P表示平地,L表示湖泊,法里奥只能停留在平地上。他目前的位置在左上角(1,1)处,而目的地为右下角的(m,n)。法里奥可以向前后左右四个方向移动或者飞行,每移动一格需要1单位时间。而飞行的时间主要花费在变形上,飞行本身时间消耗很短,所以无论一次飞行多远的距离,都只需要1单位时间。飞行的途中不能变向,并且一次飞行最终必须要降落在平地上。当然,由于受到能量的限制,法里奥不能无限制的飞行,他总共最多可以飞行的距离为D。在知道了以上的信息之后,请你帮助法里奥计算一下,他最快到达基地所需要的时间。

Input

第一行是3个正整数,m(1m100)n(1n100)D(1D100)。表示原野是m*n的矩阵,法里奥最多只能飞行距离为D

接下来的m行每行有n个字符,相互之间没有空格。P表示当前位置是平地,L则表示湖泊。假定(1,1)(m,n)一定是平地。

Output

一个整数,表示法里奥到达基地需要的最短时间。如果无法到达基地,则输出impossible 

Sample Input

4 4 2
PLLP
PPLP
PPPP
PLLP

Sample Output

5

分析:

直接用广搜法解答即可。要注意总飞行路程为D,而不是单次的飞行路程,另外不是只越过湖水的时候才飞的,平地一样可以。本题很好的说明了广度搜索的特性,即应该搜索所有同层的可能状态,而不是人为规定同层最优解,最优解是在搜索的过程中找到的。同时注意,标记是否访问的数组维度取决于状态的复杂程度,本题中因为涉及剩余飞行路程这一变量,必须令标记数组有3个维度。毕竟,不是只要到达一个点就可以,还要考虑到达时不同的剩余飞行长度对应不同的向下搜素状态。

代码:

// Problem#: 1135
// Submission#: 1867544
// 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 100

struct node{
    int x,y,step,remain;
    node( int a, int b, int c,int r ){
        x = a; y = b; step = c; remain = r;
    }
};

bool _map[MAX][MAX];
bool visit[MAX][MAX][MAX];
int move[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int m,n,d;

inline bool judge( int a, int b ){
    return a>=0 && a<m && b>=0 && b<n;
}

void bfs( int m, int n, int d ){
    memset(visit,false,sizeof(visit));
    queue<node> buffer;
    buffer.push(node(0,0,0,d));
    visit[0][0][d] = true;
    while(!buffer.empty()){
        node tmp = buffer.front();
        buffer.pop();
        if( tmp.x == m-1 && tmp.y == n-1 ){
            cout << tmp.step << endl;
            return ;
        }
        int a,b;
        int c = tmp.step + 1;
        int r = tmp.remain;
        for( int i=0 ; i<4 ; i++ ){
            a = move[i][0] + tmp.x;
            b = move[i][1] + tmp.y;
            if( judge(a,b) && _map[a][b] && !visit[a][b][r] ){
                buffer.push(node(a,b,c,r));
                visit[a][b][r] = true;
            }
            for( int j=2 ; j<=r ; j++ ){
                a += move[i][0];
                b += move[i][1];
                if( judge(a,b) && _map[a][b] && !visit[a][b][r-j] ){
                    buffer.push(node(a,b,c,r-j));
                    visit[a][b][r-j] = true;
                }
            }
        }
    }
    cout << "impossible" << endl;
}

int main(){
    char c;
    cin >> m >> n >> d;
    memset(_map,false,sizeof(_map));
    for( int i=0 ; i<m ; i++ ){
        for( int j=0 ; j<n ; j++ ){
            cin >> c;
            if( c=='P' ) _map[i][j] = true;
        }
    }
    bfs(m,n,d);
    return 0;
}

© 著作权归作者所有

上一篇: sicily 1317 Sudoku
下一篇: sicily 1210 二叉树
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
MATLAB数据矩阵单位化,归一化,标准化

原博客http://blog.csdn.net/yb536/article/details/41050181点击打开链接 1.数据矩阵单位化 方法一: %%矩阵的列向量单位化 %输出矩阵Y为单位化矩阵 %方法即是矩阵中所有元素除以该元素所在...

u012654154
2017/04/24
0
0
突然有一天明白

生、死,中间的时间用生命去丈量。活着才能证明生命的价值,而活着又难免会有快乐或者悲伤,也许更多的是介于快乐与悲伤之间的情绪。 前些天看了篇文章,作者说怎么从抑郁症中走了出来,今天...

凌云行者
2017/11/08
0
0
警惕!新版Net Transport(影音传送带)安装有猫腻

http://article.pcpop.com/show.aspx?topic_id=1317935 由于早些时候FlashGet和NetAnts(网络蚂蚁)迟迟没有新版本发布,Net Transport(影音传送带)趁虚而入,以免费且支持流媒体下载迅速获...

晨曦之光
2012/03/09
725
0
最新版本1.1.35把单引号全部替换成双引号了。。。

@wenshao 你好,想跟你请教个问题:在把字符串转为JsonArray的时候,最新版本1.1.35把里面的单引号全部替换成双引号了。。。

ALOSIN
2013/08/31
334
1

没有更多内容

加载失败,请刷新页面

加载更多

数据安全管理:RSA算法,签名验签流程详解

本文源码:GitHub·点这里 || GitEE·点这里 一、RSA算法简介 1、加密解密 RSA加密是一种非对称加密,在公开密钥加密和电子商业中RSA被广泛使用。可以在不直接传递密钥的情况下,完成加解密操...

知了一笑
29分钟前
3
0
Podman 使用指南

> 原文链接:Podman 使用指南 Podman 原来是 CRI-O 项目的一部分,后来被分离成一个单独的项目叫 libpod。Podman 的使用体验和 Docker 类似,不同的是 Podman 没有 daemon。以前使用 Docker...

米开朗基杨
今天
6
0
拯救 项目经理个人时间的5个技巧

优秀的项目经理都有一个共同点,那就是良好的时间管理能力。专业的项目经理会确保他们的时间投入富有成效,尽可能避免时间浪费。 时间管理叫做GTD,即Getting Things Done——“把事情做完”...

Airship
今天
7
0
LNMP环境介绍,Mariadb安装,服务管理,mariadb安装3

LNMP环境介绍 Nginx 处理的请求有两种,分为 静态与动态 图片,js,css,视频,音频,flash 等都是静态请求,这些数据都不是保存在数据库里面的 动态请求一般来说,需要的数据是在数据库里面...

doomcat
今天
3
0
前端技术之:Prisma Demo服务部署过程记录

安装前提条件: 1、已经安装了docker运行环境 2、以下命令执行记录发生在MackBook环境 3、已经安装了PostgreSQL(我使用的是11版本) 4、Node开发运行环境可以正常工作 首先需要通过Node包管...

popgis
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部