# Knight Shortest Path

## # Solution

All following solutions take $O(V + E)$ time and space.

### # BFS w/ HashMap

Use queue to visit nodes and dist(could also be an array or HashSet instead of HashMap) to store the distance of reaching a point.

"""
Definition for a point.
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
"""
DIRECTIONS = [(-1, -2), (-1, 2), (1, -2), (1, 2), (-2, -1), (-2, 1), (2, -1), (2, 1)]
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):
n, m = len(grid), len(grid[0])
if not n or not m: return -1
queue = [(source.x, source.y)]
dist = {(source.x, source.y): 0}

while queue:
x, y = queue.pop(0)
if (x, y)==(destination.x, destination.y):
return dist[(x, y)]
for dx, dy in DIRECTIONS:
nx, ny = x + dx, y + dy
if self.is_valid(n, m, nx, ny, grid, dist):
queue.append((nx, ny))
dist[(nx, ny)] = dist[(x, y)] + 1
return -1

def is_valid(self, n, m, x, y, grid, dist):
if not 0<=x<n or not 0<=y<m:
return False
return grid[x][y]!=1 and (x, y) not in dist

Last Updated: 7/19/2020, 3:45:14 PM