2026-11-19:象到达目标格子的最少移动步数。用go语言,在一个8行8列、坐标从1到8的方格棋盘上,有一个只能沿对角线移动的棋子。它每一步可以选择左上、右上、左下或右下方向移动任意非零格数,但不能走出棋盘。给定起点坐标 source=[sr,sc] 和终点坐标 target=[tr,tc],求该棋子从起点到达终点所需的最少步数;如果无论如何都无法到达,则返回-1。
source.length == target.length == 2。
1 <= sr, sc, tr, tc <= 8。
source != target。
输入: source = [8,1], target = [1,8]。
输出: 1。
解释:
一步对角线移动即可将象直接从 (8, 1) 送达 (1, 8)。
题目来自力扣4034。
大体步骤如下:
1. 读取起点和终点坐标
从source中取出起点的行号sr和列号sc,从target中取出终点的行号tr和列号tc。题目保证坐标都在 1 到 8 之间,并且起点和终点不相同。2. 判断起点和终点是否在“同一种颜色”的格子上
棋盘可以按(行号 + 列号)的奇偶性染成两种颜色。象每走一步都沿对角线移动,例如从(r, c)走到(r+k, c+k)、(r+k, c-k)、(r-k, c+k)或(r-k, c-k)。
无论哪种情况,行号与列号之和的奇偶性都不会改变,因此象只能到达与起点同色的格子。
代码比较(sr + sc) % 2和(tr + tc) % 2:
• 如果两者不相等,说明颜色不同,象永远无法到达目标,直接返回
-1。• 如果两者相等,继续判断需要几步。
3. 判断是否能一步到达
象一步可以沿某条对角线移动到任意格,因此如果起点和终点在同一条对角线上,就可以一步到达。
在棋盘坐标中,同一条对角线有两种情况:
• 主对角线方向:满足
sr - sc == tr - tc;• 副对角线方向:满足
sr + sc == tr + tc。
代码判断sr + sc == tr + tc或sr - sc == tr - tc是否成立。
只要其中一个成立,就说明起点和终点在同一条对角线上,返回1。
4. 处理同色但不在同一条对角线上的情况
如果起点和终点颜色相同,但它们既不在同一条主对角线上,也不在同一条副对角线上,那么象不能一步到达。
对于 8×8 棋盘上的象来说,同色格子之间最多需要两步:象可以先走到某个中间格子,使该中间格子同时位于起点所在的一条对角线和终点所在的一条对角线上,然后再从中间格子一步走到终点。
因此代码在这种情况下直接返回2。
5. 主函数调用并输出结果
主函数构造示例起点[8, 1]和终点[1, 8],调用最少步数函数,并把返回值打印出来。
对示例来说:
• 起点颜色值:
8 + 1 = 9,是奇数;• 终点颜色值:
1 + 8 = 9,也是奇数,颜色相同;• 同时
8 + 1 == 1 + 8,说明两点在同一条副对角线上;• 所以返回
1,表示象可以一步从(8,1)到达(1,8)。
6. 关于起点等于终点
题目额外给出source != target,所以本代码不需要单独处理“起点就是终点”的情况。若允许起点等于终点,则通常最少步数应为0,但这不是当前题目的输入条件。
时间复杂度:
整个算法只进行了若干次坐标读取、加法、减法和取模比较,没有循环,也没有递归。棋盘大小固定为 8×8,输入规模固定,因此总时间复杂度为O(1)。
额外空间复杂度:
算法只使用了几个整数变量保存起点和终点坐标,没有使用额外数组、队列或其他随规模增长的数据结构,因此总额外空间复杂度为O(1)。
Go完整代码如下:
package main
import (
"fmt"
)
func minBishopMoves(source, target []int)int {
sx, sy := source[0], source[1]
tx, ty := target[0], target[1]
// 颜色不同
if (sx+sy)%2 != (tx+ty)%2 {
return-1
}
// 两点之间的直线,如果斜率是 -1 或者 1,那么两点可以直接到达,否则要走两步
if sx+sy == tx+ty || sx-sy == tx-ty {
return1
}
return2
}
func main() {
source := []int{8, 1}
target := []int{1, 8}result := minBishopMoves(source, target)
fmt.Println(result)
}
Python完整代码如下:
# -*-coding:utf-8-*-
def min_bishop_moves(source, target):
sx, sy = source
tx, ty = target
# 起点和终点相同,不需要移动
if source == target:
return0
# 颜色不同,无法到达
if (sx + sy) % 2 != (tx + ty) % 2:
return-1
# 两点在同一条对角线上,可以直接到达
if sx + sy == tx + ty or sx - sy == tx - ty:
return1
# 同色但不在同一条对角线上,需要两步
return2
if __name__ == "__main__":
source = [8, 1]
target = [1, 8]result = min_bishop_moves(source, target)
print(result)
C++完整代码如下:
int minBishopMoves(const std::vector& source, const std::vector& target) {
int sx = source[0], sy = source[1];
int tx = target[0], ty = target[1];
// 颜色不同,无法到达
if ((sx + sy) % 2 != (tx + ty) % 2) {
return-1;
}
// 可选:起点等于终点时不需要移动(按题意更合理)
// if (sx == tx && sy == ty) {
// return 0;
// }
// 两点在同一条对角线上,可以一步到达;否则需要两步
if (sx + sy == tx + ty || sx - sy == tx - ty) {
return1;
}
return2;
}
int main() {
std::vector source = {8, 1};
std::vector target = {1, 8};
int result = minBishopMoves(source, target);
std::cout << result << std::endl;return0;
}
芯谷ai:xinguhub.com/sign-up?aff=txk5
我们相信人工智能为普通人提供了一种“增强工具”,并致力于分享全方位的AI知识。在这里,您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”,发消息可获得面试资料,让AI助力您的未来发展。
热门跟贴