Skip to content

Instantly share code, notes, and snippets.

@yask123
Created October 23, 2016 13:11
Show Gist options
  • Save yask123/0dd942e14f2cc2b43576cb9daeab8e11 to your computer and use it in GitHub Desktop.
Save yask123/0dd942e14f2cc2b43576cb9daeab8e11 to your computer and use it in GitHub Desktop.
from collections import deque
class Solution:
# @param N : integer
# @param M : integer
# @param x1 : integer
# @param y1 : integer
# @param x2 : integer
# @param y2 : integer
# @return an integer
def knight(self, N, M, x1, y1, x2, y2):
if x1 == x2 and y1 == y2:
return 0
knight_queue = deque([(x1,y1,0)])
level = 0
neighbours = [(1,2), (-1,2), (-1,-2), (1,-2), (2,1), (-2,1), (-2,-1),(2,-1)]
visited = set([str(x1)+str(y1)])
while len(knight_queue) > 0:
level += 1
popped_pos = knight_queue.popleft()
current_x = popped_pos[0]
current_y = popped_pos[1]
depth = popped_pos[2]
for each_neighbour in neighbours:
new_pos_x = current_x + each_neighbour[0]
new_pos_y = current_y + each_neighbour[1]
if self.in_range(new_pos_x, new_pos_y, N,M) and str(new_pos_x)+str(new_pos_y) not in visited:
if new_pos_x == x2 and new_pos_y == y2:
return depth+1
visited.add(str(new_pos_x) + str(new_pos_y))
knight_queue.append((new_pos_x, new_pos_y, depth+1))
return -1
def in_range(self, row, col, N, M):
if col >= 1 and col <= N and row >=1 and row <= M:
return True
return False
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment