小X最近对战胜韩国围棋大神李世石的AlphaGo很感兴趣,所以小X自己写了一个叫做BetaGo的人工智能程序(简称AI),这个BetaGo会做什么呢?
小X首先想要让BetaGo做到自己在棋盘上落子,这一点AlphaGo是由程序员来完成的。小X的设想是这样的:在棋盘的边框上放置一个小机器人,这个小机器人会沿着棋盘的边框移动到最接近落子点的位置,然后伸出它的机械臂将棋子放到棋盘上。这里面最关键的一步是如何让小机器人在棋盘的边框上沿着最短的路径移动,小X想请你帮他编个程序解决这个问题。
众所周知,围棋棋盘大小为 19 × 19(如下图所示),图中加粗的一圈即为边框。
我们用一对整数(x, y) 来表示棋盘上第 x 条横线(从下往上数)与第 y 条竖线(从左往右数)的交叉点,如上图中边框上的A点用(6,1)表示,B点用(10,19)表示,小机器人初始时放置在(x1,y1) 这个位置上,它想要移动到(x2, y2) 这个位置上。(x1, y1)和(x2, y2) 一定是棋盘边框上的交叉点。
每一步小机器人可以从当前位置移动到相邻(上下左右)的某个位置上,即每次可以从(x, y) 移动到(x - 1, y)、(x + 1, y)、(x, y - 1)、(x, y + 1) 四个位置中的一个,但是它不能走出或走进棋盘,也就是说它只能沿着棋盘的边框移动到相邻位置,这就意味着任一时刻相邻位置都恰好只有两个。
BetaGo 会告诉小机器人最少需要走多少步,但小X还是很担心BetaGo有的时候会失控,从而告诉他一个错误值。
为此小X只好求助你,希望你编一个程序计算从(x1, y1) 沿着棋盘的边框移动到(x2, y2) 最少需要走多少步。上图中从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)