题目背景
小 P 最喜欢玩象棋了!有一天他看到一个软件名叫《万宁象棋》,玩了几次,结果输麻了,于是他来找你帮忙。
题目描述
万宁象棋的棋盘有 n 行 m 列(可以把棋盘看做坐标系的第一象限),现在一局棋已经进入尾声。小 P 只有一个象和一个帅,象在左下角 (1,1) 的位置,而对方只有一个将在右上角 (n,m) 的位置。
已知现在小 P 先手。他每次可以移动象,象走“田”字,但不能走出棋盘外,且受到塞象眼的限制;或者也可以移动帅。假设帅的移动既不会影响象,也不会影响对方的将。
象的移动规则(了解中国象棋规则者可跳过):
象每次可以沿斜线方向走两格,即在“田”的左下角,右上角移动或在左上角,右下角移动。形式化的描述,假设象处在 (x,y) 的位置,那么下一步可以到达 (x+2,y+2)、(x+2,y−2)、(x−2,y+2)、(x−2,y−2) 这四个格子中的一个。
“塞象眼”即指“田”字的中间有棋子,也就是象走的两格的中间一格有棋子阻挡,则不能行走。
对方的将很傻,每次只会按照下 → 左 → 上 → 右的顺序走,也就是从 (n,m) 走到 (n−1,m),再走到 (n−1,m−1),然后走到 (n,m−1),最后走回 (n,m)。
请你帮忙看一看,小 P 的象能不能吃掉对方的将。如果可以,则输出最小步数;如果不可以,输出 -1
。
输入格式
仅一行两个正整数 n 和 m,表示棋盘有 n 行 m 列。
输出格式
输出仅一个数。如果可以吃掉对方的将,输出最小步数,否则输出 −1。
6 5
2
4 4
3
4 5
-1
提示
【样例 1 解释】
小 P 的象先到 (3,3),此时对方的将从 (6,5) 到达 (5,5)。下一步的象正好可以到 (5,5),吃掉将,共计 2 步。
【样例 2 解释】
小 P 先动两步帅,使得对方的将到达 (3,3),再移动象到达 (3,3),吃掉将,共计 3 步。
【数据规模与约定】
对于 100% 的数据,3≤n,m≤1018。
测试点 |
n |
m |
1 |
3≤n≤10 |
m=n |
2 |
3≤m≤10 |
3∼4 |
3≤n≤500 |
m=n |
5∼6 |
3≤m≤500 |
7∼9 |
3≤n≤105 |
m=n |
10∼12 |
3≤m≤105 |
13∼16 |
3≤n≤1018 |
m=n |
17∼20 |
3≤m≤1018 |