如何使用图算法求解船只运动？

Question

感谢您帮助解决以下问题：

游戏网格代表水域和陆地。网格包含一个 True 水的地方为 value，土地的地方为 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

上找到完整代码