P1374 进攻幽暗城

    • 33通过
    • 118提交
  • 题目提供者 kiro
  • 评测方式 云端评测
  • 标签 搜索 洛谷原创
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    由于震惊海内外的“愤怒门投毒事件”的发生,部落为了对抗皇家药剂师协会的叛乱,所有的外交工作完成后,部落大酋长萨尔带领着小A穿过传送门到达幽暗城平叛。

    题目描述

    幽暗城的地图是一个n*m的01串。a[i,j]=1时表示(i,j)的位置是障碍,无法通过;a[i,j]=0时表示(i,j)的位置可以进入。

    小A与萨尔的初始位置是(x1,y1),而恐惧魔王的初始位置是(x2,y2)。小A的目标就是到达恐惧魔王的位置。

    萨尔会按照一个特定的路线行走,该路线是一个数字串,由0-4组成。第i秒,若数字串第(i mod 数字串的长度)位=0,则表示这一秒萨尔将会原地不动;=1,则表示这一秒萨尔会向上走一格;=2,则表示这一秒萨尔会向下走一格;=3,则表示这一秒萨尔会向左走一格;=4,则表示这一秒萨尔会向右走一格。若萨尔将要移动的位置是墙或者超出迷宫的范围,则萨尔会原地不动。恐惧魔王也是这样。(换句话说,你可以认为如果将数字串是重复无限次,第i秒就是字符串第i位)

    小A每秒可以选择从上下左右四个方向中选择一个方向,朝那个方向走一格,前提是那个位置不是墙并且没有超出迷宫的范围;或者原地不动。不过,由于幽暗城的诡异环境,小A只能持续脱离萨尔的光环s秒,若超过s秒小A则会死亡。光环的有效半径为d,表示当小A与萨尔之间的距离sqrt((x-xx)^2+(y-yy)^2)小于等于d时小A才能受到萨尔光环的效果。若小A脱离萨尔的光环又重新进入光环有效区域,则再次离开光环时持续时间归零重记。

    小A想知道最少需要几秒他才能到达恐惧魔王所在的位置。

    输入输出格式

    输入格式:

    第一行四个数n,m,s,d。

    接下来的n行,每行m个数(0或1),之间没有空格,表示幽暗城的地图。

    接下来的一行四个整数,x1,y1,x2,y2(1<=x1,x2<=n,1<=y1,y2<=m)。

    接下来的一行是一个数字串,表示萨尔的移动方式。

    接下来的一行是一个数字串,表示恐惧魔王的移动方式。

    输出格式:

    一行一个整数,表示需要最少的时间。

    输入输出样例

    输入样例#1: 复制
    3 4 7 3
    1010
    0000
    0101
    1 2 3 3
    0132401
    12131
    
    输出样例#1: 复制
    3
    

    说明

    【题目来源】

    kiro原创

    【数据规模】

    对于100%的数据,1<=n,m<=50,0<=s<=1000,0<=d<=100,1=<数字串长度<=100,0<=答案<=100。

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