## 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 `true` if you can reach position [N-1, N-1] or `false` otherwise.

Empty positions are marked `.`. Walls are marked `W`. Start and exit positions are 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):
	matrix = list(map(list, maze.splitlines()))
	(stack, length) = ([[0, 0]], len(matrix))
	while len(stack):
		(x, y) = stack.pop()
		if matrix[x][y] == '.':
			matrix[x][y] = 'x'
			for (x, y) in ((x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y)):
				if 0 <= x < length and 0 <= y < length:
					stack.append((x, y))
	return matrix[length - 1][length - 1] == 'x'


def path_finder(maze):
	maze = [list(level) for level in maze.split('\n')]
	N = len(maze)
	Q = [(0, 0)]
	while Q:
		(x, y) = Q.pop(0)
		if x >= 0 and y >= 0 and (x < N) and (y < N):
			if x == N - 1 and y == N - 1:
				return True
			if maze[y][x] == '.':
				maze[y][x] = 'W'
				directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
				for (dx, dy) in directions:
					Q.append((x + dx, y + dy))
	return False


def path_finder(maze):
	g = maze.splitlines()
	(end, bag) = (len(g[0]) - 1 + len(g) * 1j - 1j, {0})
	grid = {x + y * 1j for (y, l) in enumerate(g) for (x, c) in enumerate(l) if '.' == c}
	while bag:
		if end in bag:
			return True
		grid -= bag
		bag = grid & set.union(*({z + 1j ** k for k in range(4)} for z in bag))
	return False


def path_finder(maze):
	maze = [list('W' + string + 'W') for string in maze.split('\n')]
	n = len(maze[0])
	maze = [['W'] * n] + maze + [['W'] * n]
	visited = {(i, j): 0 for i in range(n) for j in range(n)}
	visited[1, 1] = 1
	stack = [(1, 1)]
	while len(stack) > 0:
		(idx1, idx2) = stack.pop()
		if idx1 == n - 2 and idx2 == n - 2:
			return True
		if maze[idx1 - 1][idx2] == '.' and visited[idx1 - 1, idx2] == 0:
			visited[idx1 - 1, idx2] = 1
			stack.append((idx1 - 1, idx2))
		if maze[idx1][idx2 - 1] == '.' and visited[idx1, idx2 - 1] == 0:
			visited[idx1, idx2 - 1] = 1
			stack.append((idx1, idx2 - 1))
		if maze[idx1][idx2 + 1] == '.' and visited[idx1, idx2 + 1] == 0:
			visited[idx1, idx2 + 1] = 1
			stack.append((idx1, idx2 + 1))
		if maze[idx1 + 1][idx2] == '.' and visited[idx1 + 1, idx2] == 0:
			visited[idx1 + 1, idx2] = 1
			stack.append((idx1 + 1, idx2))
	return False


def path_finder(maze):
	maze = maze.split('\n')
	home = (len(maze) - 1, len(maze) - 1)
	M = {(r, c) for r in range(len(maze)) for c in range(len(maze)) if maze[r][c] == '.'} - {(0, 0)}
	P = {(0, 0)}
	while P and home not in P:
		P = {(rr, cc) for (r, c) in P for (rr, cc) in {(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)}} & M
		M -= P
	return home in P


def path_finder(maze):
	maze_object = Maze(maze)
	if maze_object.maze[maze_object.exit[0]][maze_object.exit[1]] == 'W':
		return False
	return maze_object.recursive_path((0, 0))

class Maze:
	previous_positions = []
	exit = None
	dimension_maze = None
	maze = None

	def __init__(self, maze):
		self.maze = self.transform(maze)
		self.exit = (len(self.maze) - 1, len(self.maze[0]) - 1)
		self.dimension_maze = (self.exit[0], self.exit[1])
		self.previous_positions = []

	def transform(self, maze):
		return [row for row in maze.split('\n')]

	def recursive_path(self, current_position):
		if current_position == self.exit:
			return True
		if current_position[0] > self.dimension_maze[0] or current_position[1] > self.dimension_maze[1] or current_position[0] < 0 or (current_position[1] < 0):
			return False
		if self.maze[current_position[0]][current_position[1]] == 'W':
			return False
		else:
			down = (current_position[0] + 1, current_position[1])
			up = (current_position[0] - 1, current_position[1])
			rigth = (current_position[0], current_position[1] + 1)
			left = (current_position[0], current_position[1] - 1)
			new_positions = [down, up, rigth, left]
			path_find = False
			for position in new_positions:
				if position not in self.previous_positions:
					self.previous_positions.append(position)
					path_find = path_find or self.recursive_path(position)
		return path_find


def path_finder(maze):
	maze = maze.split('\n')
	mazeD = {(x, y): 1 for (x, e) in enumerate(maze) for (y, _) in enumerate(e) if _ == '.'}
	(exit, DMap, stack) = ((len(maze) - 1, len(maze[0]) - 1), {}, [(0, 0)])
	while stack:
		(x, y) = stack.pop()
		if not DMap.get((x, y)):
			DMap[x, y] = 1
			for (xc, yc) in ((x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y)):
				if mazeD.get((xc, yc)):
					stack.append((xc, yc))
	return DMap.get(exit, 0)


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


def path_finder(maze):
	maze = maze.split('\n')
	n = len(maze)
	reachable = [[None] * (n + 2) for i in range(n + 2)]
	for i in range(n + 2):
		reachable[0][i] = False
		reachable[n + 1][i] = False
		reachable[i][0] = False
		reachable[i][n + 1] = False
	queue = [(1, 1)]
	while queue:
		(i, j) = queue.pop(0)
		reachable[i][j] = True
		for (x, y) in ((0, 1), (0, -1), (-1, 0), (1, 0)):
			(p, q) = (i + x, j + y)
			if reachable[p][q] == None:
				if maze[p - 1][q - 1] == '.':
					reachable[p][q] = True
					queue.append((p, q))
				else:
					reachable[p][q] = False
	return False if reachable[n][n] == None else reachable[n][n]


def path_finder(maze):
	grid = [list(v) for v in maze.split('\n')]
	n = len(grid)
	end = (n - 1, n - 1)

	def search(x, y):
		if (x, y) == end:
			return True
		elif grid[x][y] == 'W':
			return False
		elif grid[x][y] == 'V':
			return False
		grid[x][y] = 'V'
		if x < n - 1 and search(x + 1, y) or (y > 0 and search(x, y - 1)) or (x > 0 and search(x - 1, y)) or (y < n - 1 and search(x, y + 1)):
			return True
		return False
	return search(0, 0)