如何用图算法解决船只运动问题？

Question

感谢你的帮助来解决以下问题：

一个游戏网格表示水和陆地。网格中，水的地方用True表示，陆地的地方用False表示。
一只船可以向左或向右移动到下一个格子，或者在上下方向上移动两格。船移动的路径上的所有格子必须在网格内，并且必须是水。
请实现一个名为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))
print(can_travel_to (game_matrix, 2, 2, 2, 1))
print(can_travel_to (game_matrix, 2, 2, 2, 3))
print(can_travel_to(game_matrix, 2, 2, 4, 2))

Should print:

True
False
True
False

我通过了一个测试案例，但在另外两个案例中遇到了问题，这两个案例中所有坐标都在网格内，但有些坐标在网格外。

请查看这个链接来测试你的解决方案 TestDome

当前解决方案：

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:
        # Check that:
        # 1- the given coordinates within the grid.
        # 2- the start and end coordinates is True.
        # 3- restrict the moves (two top/down and one left/right).
        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("The indexes must be valid indexes!")

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

Answer 1

问题出在方法 can_travel_to() 上，新的更新内容是：

def can_travel_to(game_matrix, from_row, from_column, to_row, to_column):
    """Method to check if boatMovements instance is able to travel to given
    coordinates depending on starting point"""

    # Check that:
    # 1- The given coordinates within the grid.
    # 2- Restrict the steps (two when moving top/down and one left/right).
    if (to_row > len(game_matrix) - 1) or \
       (to_column > len(game_matrix[0]) - 1) or \
       (from_row != to_row and abs(to_row - from_row) != 2) or \
       (from_column != to_column and abs(to_column - from_column) != 1):

        return False

    # Check that The start and end coordinates are True, otherwise return False
    if not game_matrix[from_row][from_column] or \
       not game_matrix[to_row][to_column]:
        return False

    # Create a BoatMovements instance and set coordination of the end
    # destination.
    boat_movements = BoatMovements(game_matrix, to_row, to_column)

    # Call dfs method and return its response.
    return boat_movements.dfs_search(from_row, from_column)

注意: 你可以在 Github 上找到完整的代码