P2537 [AHOI2005]穿越磁场

    • 47通过
    • 334提交
  • 题目提供者 clearman
  • 评测方式 云端评测
  • 标签 广度优先搜索,BFS 最短路 离散化 各省省选 2005 安徽
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    探险机器人在Samuel星球上寻找一块奇特的矿石,然而此时它陷入了一片神秘的磁场区域,动弹不得。

    探险空间站立刻扫描了这片区域,绘制出该区域的磁场分布平面图。这片区域中分布了N个磁场,每个磁场呈正方形,且边与坐标轴平行。

    例如下图中,存在3个磁场,白点表示机器人的位置,黑点表示矿石的位置:

    科学家们分析平面图,进一步发现:这些磁场为大小不一的正方形,可能相交,甚至覆盖,但是它们的边缘不会重合,顶点也不会重合。

    例如下面的两种情形是不会出现的:

    科学家们给探险机器人启动了磁力罩,这样它就可以在磁场中自由穿越了。

    初始时,探险机器人和所有矿石都不在任何磁场的边缘。由于技术限制,在穿越过程中机器人只能够水平或垂直移动,且不能够沿着磁场的边缘行动。

    由于磁力罩的能量有限,科学家们希望探险机器人穿越尽量少的磁场边缘采集到这块矿石。例如上图中,探险机器人最少需要穿越两次磁场边缘。

    现在小联请你编写程序,帮助科学家们设计探险机器人的路线,统计探险机器人最少需要穿越多少次磁场边缘。

    输入输出格式

    输入格式:

    第一行有一个整数N,表示有N个磁场(1 < N < 100)。随后有N行,每行有三个整数X、Y、C(0 < X ,Y ,C < 10000),表示一个磁场左下角坐标为(X,Y),边长为C。接下来有一行,共有四个整数SX, SY, TX, TY,表示机器人初始坐标为(SX, SY),矿石坐标为(TX,TY)(其中,1 < SX, SY, TX, TY < 10000)。

    输出格式:

    单行输出一个整数,表示机器人最少需要穿越多少次磁场边缘。

    输入输出样例

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