P3818 小A和uim之大逃离 II

    • 329通过
    • 1.4K提交
  • 题目提供者 lzn
  • 评测方式 云端评测
  • 标签 广度优先搜索,BFS 搜索 最短路
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    话说上回……还是参见 https://www.luogu.org/problem/show?pid=1373

    小a和uim再次来到雨林中探险。突然一阵南风吹来,一片乌云从南部天边急涌过来,还伴着一道道闪电,一阵阵雷声。刹那间,狂风大作,乌云布满了天空,紧接着豆大的雨点从天空中打落下来,只见前方出现了一个牛头马面的怪物,低沉着声音说:“呵呵,既然你们来到这,两个都别活了!”。小a和他的小伙伴再次惊呆了!

    题目描述

    瞬间,地面上出现了一个H行W列的巨幅矩阵,矩阵的每个格子上要么是空地‘.’或者障碍'#'。

    他们起点在(1,1),要逃往(H,W)的出口。他们可以一次向上下左右移动一格,这个算一步操作。不过他们还保留着上次冒险时收集的魔液,一口气喝掉后可以瞬移到相对自己位置的(D,R)向量;也就是说,原来的位置是(x,y),然后新的位置是(x+D,y+R),这个也算一步操作,不过他们仅能至多进行一次这种操作(当然可以不喝魔液)。

    这个地方是个是非之地。所以他们希望知道最小能有几步操作可以离开这个鬼地方。不过他们可能逃不出这个鬼地方,遇到这种情况,只能等死,别无他法。

    输入输出格式

    输入格式:

    第一行个整数,H W D R,意义在描述已经说明。

    接下来H行,每行长度是W,仅有'.'或者'#'的字符串。

    输出格式:

    请输出一个整数表示最小的逃出操作次数。如果他们逃不出来,就输出-1。

    输入输出样例

    输入样例#1: 复制
    3 6 2 1
    ...#..
    ..##..
    ..#...
    输出样例#1: 复制
    5
    
    输入样例#2: 复制
    3 7 2 1
    ..#..#.
    .##.##.
    .#..#..
    输出样例#2: 复制
    -1
    输入样例#3: 复制
    6 6 -2 0
    .#....
    .#.#..
    .####.
    .#..#.
    .##.#.
    ....#.
    输出样例#3: 复制
    21

    说明

    样例解释1

    (1,1)→(1,2)→(1,3)→喝(3,4)→(3,5)→(3,6)

    样例解释2

    因为只有一瓶魔液所以他们没办法逃出来

    样例解释3

    D和R还可以是0或者负数。

    数据范围与约定

    40%的测试数据2<=H,W<=5

    70%的测试数据2<=H,W<=100

    100%的测试数据2<=H,W<=1000,|D|<H,|R|<W

    标程展开

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。