# Knight Shortest Path

BFSDP

## # Input & Output

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

1
2
3
4

## # Solution

Let $n$ be the number of rows and $m$ be the number of columns. All following solutions take $O(V + E) = O(nm)$ time and space.

### # Definition for a point

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

1
2
3
4

### # 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.

DIRECTIONS = [(-1, -2), (-1, 2), (1, -2), (1, 2), (-2, -1), (-2, 1), (2, -1), (2, 1)]
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22