船只移动问题的图算法实现求助：can_travel_to函数测试未通过

需求说明 #

现有游戏网格中，True代表水域、False代表陆地。船只允许一步移动：左右移动1格，或上下移动2格；移动路径上的所有格子（包括起点和终点）必须处于网格内且为水域。需实现can_travel_to函数，接收网格矩阵、起始点与目标点坐标，返回布尔值表示两点能否一步到达。

测试示例 #

game_matrix = [
    [False, False, True, True, False],
    [False, False, True, False, False],
    [False, False, True, True, False],
    [False, True, False, True, False],
    [False, False, True, False, False]
]

print(can_travel_to(game_matrix, 2, 2, 0, 2))  # 应输出 True
print(can_travel_to(game_matrix, 2, 2, 2, 1))  # 应输出 False
print(can_travel_to(game_matrix, 2, 2, 2, 3))  # 应输出 True
print(can_travel_to(game_matrix, 2, 2, 4, 2))  # 应输出 False

当前实现代码 #

class BoatMovements:
    def __init__(self, matrix, to_row, to_column):
        self.row = to_row
        self.column = to_column
        self.matrix = matrix
        self.visited = [
            [False for _ in range(len(matrix[0]))]
            for _ in range(len(matrix))
        ]

    def valid_move(self, row, column):
        if 0 <= row < len(self.matrix) and 0 <= column < len(self.matrix[0]):
            if self.matrix[row][column] and not self.visited[row][column]:
                return True
        return False

    def dfs_search(self, row, column):
        if not self.valid_move(row, column):
            return False
        if self.row == row and self.column == column:
            return True
        self.visited[row][column] = True
        return (self.dfs_search(row - 1, column) or
                self.dfs_search(row, column - 1) or
                self.dfs_search(row + 1, column) or
                self.dfs_search(row, column + 1))


def can_travel_to(game_matrix, from_row, from_column, to_row, to_column):
    try:
        # 检查：
        # 1- 坐标在网格内
        # 2- 起点和终点是水域
        # 3- 移动范围限制（上下最多2格，左右最多1格）
        if (to_row > len(game_matrix) - 1) or \
           (to_column > len(game_matrix) - 1) or \
           not game_matrix[from_row][from_column] or \
           not game_matrix[to_row][to_column] or \
           abs(to_row - from_row) > 2 or \
           abs(to_column - from_column) > 1:
            return False
    except IndexError:
        raise IndexError("索引必须有效！")

    boat_movements = BoatMovements(game_matrix, to_row, to_column)
    return boat_movements.dfs_search(from_row, from_column)

问题排查与修正 #

你的代码存在几个核心问题，导致坐标合法性和越界测试用例失败：

• 坐标合法性检查错误：仅判断了终点坐标的合法性，未检查起点坐标；列数判断错误使用了len(game_matrix)-1，正确应为len(game_matrix[0])-1，非正方形网格会触发错误判断。
• 错误使用DFS逻辑：题目要求的是一步到达，不需要DFS遍历多步路径，属于过度设计。
• 移动规则判断不完整：上下移动2格时，未检查中间格子是否为水域，这是路径合法性的必要条件。

修正后的代码 #

def can_travel_to(game_matrix, from_row, from_column, to_row, to_column):
    rows = len(game_matrix)
    if rows == 0:
        return False
    cols = len(game_matrix[0])
    
    # 检查所有坐标是否在网格范围内
    if not (0 <= from_row < rows and 0 <= from_column < cols):
        return False
    if not (0 <= to_row < rows and 0 <= to_column < cols):
        return False
    
    # 检查起点和终点是否为水域
    if not game_matrix[from_row][from_column] or not game_matrix[to_row][to_column]:
        return False
    
    # 同一坐标直接返回True
    if from_row == to_row and from_column == to_column:
        return True
    
    # 左右移动1格的情况
    if from_row == to_row:
        return abs(from_column - to_column) == 1
    # 上下移动2格的情况，需检查中间格子
    elif abs(from_row - to_row) == 2 and from_column == to_column:
        mid_row = (from_row + to_row) // 2
        return game_matrix[mid_row][from_column]
    # 不符合任何一步移动规则
    else:
        return False

修正说明 #

1. 完整校验所有坐标的合法性，避免越界错误；
2. 严格按照一步移动规则判断：左右移动仅需行列差符合要求，上下移动需额外校验中间格子的水域属性；
3. 移除不必要的DFS逻辑，简化判断逻辑，符合题目需求。

内容的提问来源于stack exchange，提问作者Wadhah Sky