knight.py

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