## Task

You are at position `[0, 0]` in maze NxN and you can **only** move in one of the four cardinal directions (i.e. North, East, South, West). Return the minimal number of steps to exit position `[N-1, N-1]` *if* it is possible to reach the exit from the starting position.  Otherwise, return `false` in **JavaScript**/**Python** and `-1` in **C++**/**C#**/**Java**.

Empty positions are marked `.`.  Walls are marked `W`.  Start and exit positions are guaranteed to be empty in all test cases.

## Path Finder Series:

-       [#1: can you reach the exit?](https://www.codewars.com/kata/5765870e190b1472ec0022a2)
-       [#2: shortest path](https://www.codewars.com/kata/57658bfa28ed87ecfa00058a)
-       [#3: the Alpinist](https://www.codewars.com/kata/576986639772456f6f00030c)
-       [#4: where are you?](https://www.codewars.com/kata/5a0573c446d8435b8e00009f)
-       [#5: there's someone here](https://www.codewars.com/kata/5a05969cba2a14e541000129)

Source: codewars | Difficulty: MEDIUM

Starter code: def path_finder(maze):
	

Solutions:
def path_finder(maze):
	lst = maze.split('\n')
	(X, Y) = (len(lst) - 1, len(lst[0]) - 1)
	seen = {(x, y) for (x, row) in enumerate(lst) for (y, c) in enumerate(row) if c == 'W'} | {(0, 0)}
	(end, bag, turn) = ((X, Y), {(0, 0)}, 0)
	while bag and end not in bag:
		bag = {(a, b) for (a, b) in {(x + dx, y + dy) for (x, y) in bag for (dx, dy) in ((0, 1), (0, -1), (1, 0), (-1, 0))} if 0 <= a <= X and 0 <= b <= Y} - seen
		seen |= bag
		turn += 1
	return bool(bag) and turn


def path_finder(maze):
	maze_arr = maze_str_to_array(maze)
	n = len(maze_arr)
	(start, goal) = ((0, 0), (n - 1, n - 1))
	return ai_star(maze_arr, start, goal)

def bfs(maze_arr, start, goal):
	from queue import Queue
	to_be_expanded = Queue()
	to_be_expanded.put(start)
	tree = set()
	while not to_be_expanded.empty():
		node = to_be_expanded.get()
		if node == goal:
			return True
		tree.add(node)
		neighbors = get_node_neighbors(maze_arr, node)
		for neighbor in neighbors:
			if neighbor not in tree:
				to_be_expanded.put(neighbor)
	return False

def ai_star(maze_arr, start, goal):
	from heapq import heappush, heappop
	to_be_expanded = []
	heappush(to_be_expanded, (manhattan_distance(start, goal), 0, 0, start))
	tree = set()
	while to_be_expanded:
		(_, cost, real_cost, node) = heappop(to_be_expanded)
		if node == goal:
			return real_cost
		tree.add(node)
		neighbors = get_node_neighbors(maze_arr, node)
		for neighbor in neighbors:
			if neighbor not in tree:
				heappush(to_be_expanded, (cost + manhattan_distance(neighbor, goal), cost + 0.99, real_cost + 1, neighbor))
	return False

def manhattan_distance(cell, goal):
	return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])

def euclidean_distance(cell, goal):
	from math import sqrt
	return sqrt((cell[0] - goal[0]) ** 2 + (cell[1] - goal[1]) ** 2)

def maze_str_to_array(maze):
	return [[1 if char == '.' else 0 for char in row] for row in maze.split('\n')]

def get_node_neighbors(maze_arr, parent_node):
	n = len(maze_arr)
	neighbors = []
	(x_0, y_0) = parent_node
	for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
		x_1 = x_0 + dx
		y_1 = y_0 + dy
		if 0 <= x_1 < n and 0 <= y_1 < n and (maze_arr[y_1][x_1] == 1):
			neighbors.append((x_1, y_1))
	return neighbors


from math import hypot
from heapq import *
MOVES = ((0, 1), (0, -1), (1, 0), (-1, 0))

def path_finder(maze):
	maze = list(map(list, maze.split()))
	(X, Y) = end = (len(maze) - 1, len(maze[0]) - 1)
	q = [(0, 0, 0, (0, 0))]
	while q and (not q[0][1]):
		(_, _, c, (x, y)) = heappop(q)
		c += 1
		for (dx, dy) in MOVES:
			pos = (a, b) = (x + dx, y + dy)
			if 0 <= a <= X and 0 <= b <= Y and (maze[a][b] != 'W'):
				maze[a][b] = 'W'
				heappush(q, (c + X - a + Y - b, pos == end, c, pos))
	return q and q[0][1] and q[0][2] or 0


def path_finder(maze):
	matrix = list(map(list, maze.splitlines()))
	n = len(matrix) - 1
	(lst, lst2, count) = ([(0, 0)], [], 0)
	while lst:
		count += 1
		while lst:
			(a, b) = lst.pop()
			matrix[a][b] = 'X'
			for (i, j) in ((a + 1, b), (a - 1, b), (a, b + 1), (a, b - 1)):
				if 0 <= i <= n and 0 <= j <= n and (matrix[i][j] == '.'):
					if i == n and j == n:
						return count
					lst2.append((i, j))
		(lst, lst2) = (list(set(lst2)), [])
	return False


def path_finder(maze):
	maze = list(map(list, maze.splitlines()))
	(lenmaze_y, lenmaze_x) = (len(maze), len(maze[0]))
	queue = [(0, 0, 0)]
	while queue:
		(y, x, cnt) = queue.pop(0)
		if x >= 0 and y >= 0 and (x < lenmaze_x) and (y < lenmaze_y):
			if maze[y][x] == '.':
				maze[y][x] = cnt
				directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
				for (direction_y, direction_x) in directions:
					queue.append((y + direction_y, x + direction_x, cnt + 1))
			if x == lenmaze_x - 1 and y == lenmaze_y - 1:
				return maze[y][x]
	return False


def path_finder(maze):
	grid = maze.splitlines()
	end = (h, w) = (len(grid) - 1, len(grid[0]) - 1)
	(bag, seen) = ({(0, 0): 0}, set())
	while bag:
		(x, y) = min(bag, key=bag.get)
		rounds = bag.pop((x, y))
		seen.add((x, y))
		if (x, y) == end:
			return rounds
		for (u, v) in ((-1, 0), (0, 1), (1, 0), (0, -1)):
			(m, n) = (x + u, y + v)
			if (m, n) in seen or not (0 <= m <= h and 0 <= n <= w) or grid[m][n] != '.':
				continue
			new_rounds = rounds + 1
			if new_rounds < bag.get((m, n), float('inf')):
				bag[m, n] = new_rounds
	return False


def path_finder(maze):
	mtx = list(map(list, maze.splitlines()))
	R = len(mtx[0])
	mtx[R - 1][R - 1] = 'E'
	(sr, sc) = (0, 0)
	(rq, cq) = ([], [])
	prev = [[' '] * R for x in range(R)]
	move_count = 0
	nodes_left_in_layer = 1
	nodes_in_next_layer = 0
	reached_end = False
	visited = [[False] * R for x in range(R)]
	dr = [-1, 1, 0, 0]
	dc = [0, 0, 1, -1]
	rq.append(sr)
	cq.append(sc)
	visited[sr][sc] = True
	while len(rq):
		r = rq.pop(0)
		c = cq.pop(0)
		if mtx[r][c] == 'E':
			reached_end = True
			return move_count
		for i in range(4):
			rr = r + dr[i]
			cc = c + dc[i]
			if rr < 0 or cc < 0:
				continue
			if rr >= R or cc >= R:
				continue
			if visited[rr][cc]:
				continue
			if mtx[rr][cc] == 'W':
				continue
			rq.append(rr)
			cq.append(cc)
			visited[rr][cc] = True
			prev[rr][cc] = [r, c]
			nodes_in_next_layer += 1
		nodes_left_in_layer -= 1
		if nodes_left_in_layer == 0:
			nodes_left_in_layer = nodes_in_next_layer
			nodes_in_next_layer = 0
			move_count += 1
	if reached_end:
		return move_count
	else:
		return False


class Path:

	def __init__(self, maze, start, exit=None, pos='.'):
		self.maze = maze
		self.MAPd = {start: 1}
		self.exit = exit or (len(maze) - 1, len(maze[0]) - 1)
		self.grow = None
		self.pos = pos

	def run_maze(self):
		self.grow = self.len_
		for (x, floor) in enumerate(self.maze):
			for (y, _) in enumerate(floor):
				if self.maze[x][y] == self.pos and (not self.MAPd.get((x, y))):
					self.mover(x, y, [])

	def mover(self, x, y, ways=[]):
		[not self.MAPd.get(e) or ways.append(self.MAPd[e]) for e in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1))]
		if ways:
			self.MAPd[x, y] = min(ways) + 1

	@property
	def len_(self):
		return len(self.MAPd)

	@property
	def new_way_exist(self):
		return self.grow != self.len_

	@property
	def get_exit(self):
		return self.MAPd.get(self.exit, 1) - 1

def path_finder(maze):
	mazer = Path(maze.split('\n'), (0, 0))
	while mazer.new_way_exist:
		mazer.run_maze()
	return mazer.get_exit


def path_finder(maze):
	maze = maze.split('\n')
	(x_, y_) = (len(maze) - 1, len(maze[0]) - 1)
	(DMap, exit) = ({(0, 0): 1}, (x_, y_))
	while 1:
		chkr = len(DMap)
		for (x, r) in enumerate(maze):
			for (y, c) in enumerate(r):
				if maze[x][y] == '.' and (not DMap.get((x, y))):
					ways = []
					for e in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
						not DMap.get(e) or ways.append(DMap[e])
					if ways:
						DMap[x, y] = min(ways) + 1
		if chkr == len(DMap):
			break
	return DMap.get(exit, 1) - 1


def path_finder(maze):
	maze = maze.split('\n')
	inf = 2147483647
	n = len(maze)
	distance_table = [[-1] * (n + 2) for i in range(n + 2)]
	for i in range(n + 2):
		distance_table[0][i] = inf
		distance_table[n + 1][i] = inf
		distance_table[i][0] = inf
		distance_table[i][n + 1] = inf
	distance_table[1][1] = 0
	queue = [(1, 1)]
	while queue:
		(i, j) = queue.pop(0)
		for (x, y) in ((0, 1), (0, -1), (-1, 0), (1, 0)):
			(p, q) = (i + x, j + y)
			if distance_table[p][q] < inf:
				if maze[p - 1][q - 1] == 'W':
					distance_table[p][q] = inf
				elif distance_table[p][q] == -1 or distance_table[p][q] > distance_table[i][j] + 1:
					distance_table[p][q] = distance_table[i][j] + 1
					queue.append((p, q))
	return False if distance_table[n][n] == -1 else distance_table[n][n]