[Python] How to solve boat movements using Graph algorithm? [closed]

Appreciate your help to solve the following issue:

A game grid represents water and land masses. The grid contains a True value where it's water and False where it's land. A boat can go to the next tile in the left or right directions, or move twice in the top and bottom directions. All the tiles in the path must be inside the grid and contain water. Implement the can_travel_to function, which accepts a grid matrix, starting and destination coordinates (row and column), and returns a boolean indicating whether a boat can travel between the two points in one step.

For example, the following code:

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​

I pass one case of tests but I can't with the other two which in case all coordinates inside the grid and some coordinates are outside the grid.

Check this link to test your solution TestDome

Current solution:


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)

Continue reading...