#530. 【入门】小 X 与机器人 (betago)

【入门】小 X 与机器人 (betago)

说明

小 X 最近对战胜韩国围棋大神李世石的 AlphaGo 很感兴趣,所以小 X 自己写了一个叫 做 BetaGo的人工智能程序(简称 AI) , 这个 BetaGo 会做什么呢?

小 X 首先想要让 BetaGo 做到自己在棋盘上落子, 这一点 AlphaGo 是由程序员来完成的。小 X 的设想是这样的: 在棋盘的边框上放置一个小机器人, 这个小机器人会沿着棋盘的边框移动到最接近落子点的位置,然后伸出它的机械臂将棋子放到棋盘上。 这里面最关键的一步是如何让小机器人在棋盘的边框上沿着最短的路径移动,小 X 想请你帮他编个程序解决这个问题。

众所周知,围棋棋盘大小为 19 × 19(如下图所示) , 图中加粗的一圈即为边框。

我们用一对整数 (x,yx, y) 来表示棋盘上第x x 条横线(从下往上数)与第y y 条竖线(从左往右数)的交叉点,如上图中边框上的 A 点用( 6, 1) 表示, B 点用 (10, 19) 表示,小机器人初始时放置在 (x1,y1x_1,y_1) 这个位置上, 它想要移动到 (x2,y2x_2, y_2) 这个位置上。

(x1,y1x_1, y_1) 和(x2,y2x_2, y_2) 一定是棋盘边框上的交叉点每一步小机器人可以从当前位置移动到相邻(上下左右)的某个位置上, 即每次可以从 (x,yx, y) 移动到$ (x - 1, y) 、 (x + 1, y) 、 (x, y - 1) 、 (x, y + 1) $四个位置中的一个, 但是它不能走出或走进棋盘,也就是说它只能沿着棋盘的边框移动到相邻位置, 这就意味着任一时刻相邻位置都恰好只有两个。

BetaGo 会告诉小机器人最少需要走多少步, 但小 X 还是很担心 BetaGo 有的时候会失控,从而告诉他一个错误值。

为此小 X 只好求助你, 希望你编一个程序计算从 (x1,y1x_1, y_1) 沿着棋盘的边框移动到 (x2,y2x_2, y_2) 最少需 要 走 多 少步 。 上 图 中 从 A 点 ( 6 , 1 ) 移 动 到 B 点 (10 , 19) 最 少需 要 走 32 步 , 移 动 路线 是 :( 6 , 1 ) → ( 5 , 1 ) → ( 4 , 1 ) → ( 3 , 1 ) → ( 2 , 1 ) → ( 1 , 1 ) → (1 , 2 ) → (1 , 3 ) →……→(1, 19) →(2, 19) →……→(10, 19)

输入格式

输入数据仅有一行包含四个用空格隔开的正整数表示 x1,y1,x2,y2x_1, y_1, x_2, y_2 数据保证(x1,y1)(x2,y2) (x_1, y_1) , (x_2, y_2) 一定是棋盘边框上的交叉点。

输出格式

输出一行包含一个整数 ans, 表示小机器人从 (x1,y1)(x_1, y_1) 移动到 (x2,y2x_2, y_2) 的最少步数。

样例

6 1 10 19
32

数据范围

对于 30%的数据,(x1,y1)(x2,y2) (x_1, y_1) , (x_2, y_2) 在同一条边框上

对于另外 30%的数据, (x1,y1)(x2,y2)(x_1, y_1) , (x_2, y_2) 在相邻的两条边框上

对于另外 40%的数据, (x1,y1)(x2,y2)(x_1, y_1) , (x_2, y_2) 在相对的两条边框上

友情提醒

在计算机语言中, 绝对值函数常记作 abs(x) , 绝对值函数的值一定大于等于 0, 其意义为 x 到 0的距离,如 3 到 0 的距离为3, -3到0的距离也是 3,所以 abs(3) =abs(-3) =3,一般地有 abs(x1x2)=abs(x2x1)x1abs(x_1-x_2) =abs(x_2-x_1) =x_1x2x_2的距离。

来源

常州市2016“信息与未来”夏令营选拔赛