Knight Shortest Path – Python 3 (Week 14 – 05）

"""
Definition for a point.
class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b
"""

class Solution:
    """
    @param grid: a chessboard included 0 (false) and 1 (true)
    @param source: a point
    @param destination: a point
    @return: the shortest path 
    """

    def shortestPath(self, grid, source, destination):
        # write your code here
        DIRECTIONS = [(-2, -1), (-2, 1), (-1, 2), (1, 2),(2, 1), (2, -1), (1, -2), (-1, -2)]
        queue = collections.deque([(source.x, source.y)])
        distance = {(source.x, source.y): 0}
        while queue:
            x, y = queue.popleft()
            if (x, y) == (destination.x, destination.y):
                    return distance[(x, y)]
            for dx, dy in DIRECTIONS:
                next_x, next_y = x + dx, y + dy
                if (next_x, next_y) in distance:
                    continue 
                if self.is_not_valid(next_x, next_y, grid):
                    continue
                distance[(next_x, next_y)] = distance[(x, y)] + 1
                queue.append((next_x, next_y))
          
        return -1
        
    def is_not_valid(self, x, y, grid):
        n, m = len(grid), len(grid[0])
        if x < 0 or x >= n or y < 0 or y >= m:
            return True
        return grid[x][y]