Find the length of the shortest path for a knight to travel from the source point to the destination point in a chessboard. Return -1 if no path can be found.
Example
I: board = # 0 is open 1 is blocked
[[0,0,0],
[0,0,0],
[0,0,0]]
source = [2, 0]
destination = [2, 2]
O: 2 because (2, 0) -> (0, 1) -> (2, 2)
I: board =
[[0,1,0],
[0,0,1],
[0,0,0]]
source = [2, 0] destination = [2, 2]
Output: -1 because no possible path
Analysis
A simple bidirectional graph where the vertex is the position and the edge is a possible knight move from one position to another position. Searching for length on a simple graph is just BFS. A check in pre visit has to determine the next position is in-bound and open.
Code
from typing import Deque, List, Set, Tuple
from collections import deque
def shortestPath(
grid: List[List[bool]], source: Point, destination: Point
) -> int:
queue: Deque[Point] = deque()
# hash(Point) is the memory address
# hash(Tuple) computes the hash of each element then combine (XOR) them
visited_set: Set[Tuple[int, int]] = set()
queue.append(source)
visited_set.add((source.x, source.y))
levels = 0
while len(queue) > 0:
level_size = len(queue)
for i in range(level_size):
cur_point = queue.popleft()
if cur_point.x == destination.x and cur_point.y == destination.y:
return levels
for step in find_next_steps(cur_point):
if not is_in_bound(grid, step):
continue
if grid[step.x][step.y]:
continue
if (step.x, step.y) in visited_set:
continue
queue.append(step)
visited_set.add((step.x, step.y))
levels += 1
return -1
def find_next_steps(pt: Point) -> List[Point]:
return [
Point(pt.x + 1, pt.y + 2),
Point(pt.x + 1, pt.y - 2),
Point(pt.x - 1, pt.y + 2),
Point(pt.x - 1, pt.y - 2),
Point(pt.x + 2, pt.y + 1),
Point(pt.x + 2, pt.y - 1),
Point(pt.x - 2, pt.y + 1),
Point(pt.x - 2, pt.y - 1),
]
def is_in_bound(grid: List[List[bool]], pt: Point) -> bool:
boundary_m = len(grid)
boundary_n = len(grid[0])
return pt.x >= 0 and pt.y >= 0 and pt.x < boundary_m and pt.y < boundary_n
Code
CPython default hash function for custom class is its memory address. You have to write a custom hash to dedup the equivalent values.
def shortestPath(
grid: List[List[bool]], source: Point, destination: Point
) -> int:
queue: Deque[Point] = deque()
visited_set: Set[Point] = set()
queue.append(source)
visited_set.add(custom_hash(source))
levels = 0
while len(queue) > 0:
level_size = len(queue)
for i in range(level_size):
cur_point = queue.popleft()
if cur_point.x == destination.x and cur_point.y == destination.y:
return levels
for step in find_next_steps(cur_point):
if not is_in_bound(grid, step):
continue
if grid[step.x][step.y]:
continue
if custom_hash(step) in visited_set:
continue
queue.append(step)
visited_set.add(custom_hash(step))
levels += 1
return -1
def custom_hash(pt: Point) -> int:
return pt.x * 13 ** 1 + pt.y * 29 ** 2
