Created
October 23, 2016 13:11
Star
You must be signed in to star a gist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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