# Rather than checking if all possibles moves, iterate over
# obstacles and check if they are on the queen path.
# We find the minimum distances in each direction.

# Calculate max distances in all directions
dir_w = r_q - 1
dir_e = n - r_q
dir_n = c_q - 1
dir_s = n - c_q

dir_nw = min(dir_n, dir_w)
dir_sw = min(dir_s, dir_w)
dir_ne = min(dir_n, dir_e)
dir_se = min(dir_s, dir_e)

# Find obstacles that are on queens way
# and calculate the distances
for obs in obstacles:

		# Horizontal
		if obs[0] == r_q:
				if obs[1] < c_q:
						# W
						dist = c_q - obs[1] - 1
						if dist < dir_w:
								dir_w = dist
				else:
						# E
						dist = obs[1] - c_q - 1
						if dist < dir_e:
								dir_e = dist

		# Vertical
		elif obs[1] == c_q:
				if obs[0] < r_q:
						# N
						dist = r_q - obs[0] - 1
						if dist < dir_n:
								dir_n = dist
				else:
						# E
						dist = obs[0] - r_q - 1
						if dist < dir_s:
								dir_s = dist

		# Diagonals
		elif abs(obs[0] - r_q) == abs(obs[1] - c_q):
				# Decreasing diagonal: (1,1), (2,2), (3,3)
				# NW to SE
				if obs[0] - r_q == obs[1] - c_q:
						if obs[0] < r_q:
								# NW
								dist = r_q - obs[0] - 1
								if dir_nw > dist:
										dir_nw = dist
						else:
								# SE
								dist = obs[0] - r_q - 1
								if dir_se > dist:
										dir_se = dist

				# Increasing diagonal: (1,3), (2,2), (3,1)
				elif obs[0] - r_q == -(obs[1] - c_q):
						if obs[0] < r_q:
								# SW
								dist = r_q - obs[0] - 1
								if dir_sw > dist:
										dir_sw = dist
						else:
								# NE
								dist = obs[0] - r_q - 1
								if dir_ne > dist:
										dir_ne = dist