Kate constantly finds herself in some kind of a maze. Help her to find a way out!.

For a given maze and Kate's position find if there is a way out. Your function should return True or False.

Each maze is defined as a list of strings, where each char stays for a single maze "cell". ' ' (space) can be stepped on, '#' means wall and 'k' stays for Kate's starting position. Note that the maze may not always be square or even rectangular.

Kate can move left, up, right or down only.

There should be only one Kate in a maze. In any other case you have to throw an exception.


Example input
=============
```
['# ##',
 '# k#',
 '####']
```

Example output
==============
True

Example input
=============
```
['####'.
 '# k#',
 '####']
```

Example output
==============
False

Difficulty: MEDIUM
Tags: Data structures

Complete search
Skill types: Data structures

Complete search

Starter code:
def has_exit(maze):
	

Solutions:
MOVES = {(0, 1), (0, -1), (1, 0), (-1, 0)}

def has_exit(maze):
	posSet = {(x, y) for x in range(len(maze)) for y in range(len(maze[x])) if maze[x][y] == 'k'}
	if len(posSet) != 1:
		raise ValueError("There shouldn't be more than one kate")
	seen = set(posSet)
	while posSet:
		(x, y) = posSet.pop()
		if any((not (0 <= x + dx < len(maze) and 0 <= y + dy < len(maze[x + dx])) for (dx, dy) in MOVES)):
			return True
		neighbors = {(x + dx, y + dy) for (dx, dy) in MOVES if 0 <= x + dx < len(maze) and 0 <= y + dy < len(maze[x + dx]) and (maze[x + dx][y + dy] == ' ') and ((x + dx, y + dy) not in seen)}
		posSet |= neighbors
		seen |= neighbors
	return False


def has_exit(maze):
	W = len(maze[0])
	S = W * len(maze)
	(frontier, unseen) = (set(), set())
	for (position, content) in enumerate(''.join(maze)):
		(frontier.add, unseen.add, id)['k #'.index(content)](position)
	assert len(frontier) == 1
	while frontier:
		position = frontier.pop()
		if min(position, S - position) < W or -~position % W < 2:
			return True
		for way in (position - W, position + W, position - 1, position + 1):
			if way in unseen:
				frontier.add(way)
				unseen.remove(way)
	return False


def has_exit(m):
	maze = [[x for x in row] for row in m]
	if not check_edge(maze):
		return False
	if not check_kate(maze):
		raise Exception('There should no be multiple Kates')
	kate = find_kate(maze)
	return find_way(maze, kate, kate)

def find_way(maze, position, previous_position, trace=[]):
	if is_exit(maze, position):
		return True
	possible_ways = find_possible_ways(maze, position, previous_position)
	for possible_way in possible_ways:
		if possible_way not in trace:
			new_maze = move_kate(maze, possible_way, position)
			if find_way(new_maze, possible_way, position, trace + [possible_way]):
				return True
	return False

def find_possible_ways(maze, position, previous_position):
	(r, c) = position
	possible_ways = []
	for (pr, pc) in [(r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)]:
		if pr >= 0 and pr < len(maze) and (pc >= 0) and (pc < len(maze[0])):
			if maze[pr][pc] == ' ' and (pr, pc) != previous_position:
				possible_ways += [(pr, pc)]
	return possible_ways

def find_kate(maze):
	for r in range(len(maze)):
		for c in range(len(maze[0])):
			if maze[r][c] == 'k':
				return (r, c)

def move_kate(maze, new_position, previous_position):
	(nr, nc) = new_position
	(pr, pc) = previous_position
	new_m = maze[:pr] + [maze[pr][:pc] + [' '] + maze[pr][pc + 1:]] + maze[pr + 1:]
	return new_m[:nr] + [new_m[nr][:nc] + ['k'] + new_m[nr][nc + 1:]] + new_m[nr + 1:]

def check_edge(maze):
	edges = maze[0] + maze[-1] + tr(maze)[0] + tr(maze)[-1]
	if ' ' in edges or 'k' in edges:
		return True
	return False

def check_kate(maze):
	count = 0
	for r in range(len(maze)):
		for c in range(len(maze[0])):
			if maze[r][c] == 'k':
				count += 1
	return count == 1

def is_exit(maze, position):
	(width, length) = (len(maze) - 1, len(maze[0]) - 1)
	if width in position or length in position or 0 in position:
		return True
	return False

def tr(mtx):
	return [list(x) for x in zip(*mtx)]


def has_exit(maze):
	(vector, w) = (list(''.join(maze)), len(maze[0]))
	assert vector.count('k') == 1
	while 'k' in vector:
		for (p, cell) in enumerate(vector):
			if cell == 'k':
				if min(p, len(vector) - p) < w or -~p % w < 2:
					return True
				for direction in (-w, 1, w, -1):
					if vector[p + direction] == ' ':
						vector[p + direction] = 'k'
				vector[p] = '+'
	return False


from copy import deepcopy
import queue

class MazeSymbols(object):
	START_TILE = 'k'
	WALL_TILE = '#'
	WALKABLE_TILE = ' '

class MazeStatus(object):
	FOUND_EXIT = 1
	NO_EXIT_EXISTS = 2
	CONTINUE_SEARCH = 3
	MAZE_VALID = 4
	MAZE_ERROR_NO_START = 5
	MAZE_ERROR_DUPLICATE_START = 6

class MazeSolver(object):

	def __init__(self, mazeBoard):
		self.mazeBoard = deepcopy(mazeBoard)
		self.numRows = len(self.mazeBoard)
		self.numCols = len(self.mazeBoard[0])
		(validStatus, startRow, startCol) = self.__validateMaze__(self.mazeBoard)
		if validStatus == MazeStatus.MAZE_VALID:
			self.validMaze = True
		else:
			self.validMaze = False
		self.startRow = startRow
		self.startCol = startCol

	def isValidMaze(self):
		return self.validMaze

	def attemptSolve(self):
		nR = self.numRows
		nC = self.numCols
		hasVisited = [[False for _ in range(nC)] for _ in range(nR)]
		mazeWalkResult = self.__walkMaze__(self.mazeBoard, hasVisited, nR, nC, self.startRow, self.startCol)
		return mazeWalkResult

	def __validateMaze__(self, mazeBoard):
		startPos = self.__findStartPosition__(mazeBoard)
		if not startPos:
			return (MazeStatus.MAZE_ERROR_NO_START, -1, -1)
		elif len(startPos) >= 2:
			return (MazeStatus.MAZE_ERROR_DUPLICATE_START, -1, -1)
		else:
			startRow = startPos[0][0]
			startCol = startPos[0][1]
			return (MazeStatus.MAZE_VALID, startRow, startCol)

	def __findStartPosition__(self, mazeBoard):
		startPos = []
		for i in range(self.numRows):
			for j in range(self.numCols):
				if self.mazeBoard[i][j] == MazeSymbols.START_TILE:
					startPos.append([i, j])
		return startPos

	def __inImage__(self, i, j, nR, nC):
		if 0 <= i and i < nR and (0 <= j) and (j < nC):
			return True
		else:
			return False

	def __isDesiredCell__(self, img, hasVisited, i, j):
		if img[i][j] == MazeSymbols.WALKABLE_TILE and (not hasVisited[i][j]):
			return True
		else:
			return False

	def __markCellAsVisited__(self, hasVisited, i, j):
		hasVisited[i][j] = True

	def __foundExit__(self, curR, curC, nR, nC):
		upStep = curR - 1
		downStep = curR + 1
		leftStep = curC - 1
		rightStep = curC + 1
		if not self.__inImage__(upStep, curC, nR, nC):
			return True
		elif not self.__inImage__(downStep, curC, nR, nC):
			return True
		elif not self.__inImage__(curR, leftStep, nR, nC):
			return True
		elif not self.__inImage__(curR, rightStep, nR, nC):
			return True
		else:
			return False

	def __foundDuplicateStartPos__(self, img, curR, curC):
		if img[curR][curC] == MazeSymbols.START_TILE:
			return True
		else:
			return False

	def __checkMazeStatus__(self, img, curR, curC, nR, nC):
		if self.__foundExit__(curR, curC, nR, nC):
			return MazeStatus.FOUND_EXIT
		elif self.__foundDuplicateStartPos__(img, curR, curC):
			return MazeStatus.MAZE_ERROR_DUPLICATE_START
		else:
			return MazeStatus.CONTINUE_SEARCH

	def __walkMaze__(self, img, hasVisited, nR, nC, iRoot, jRoot):
		di = [0, 0, 1, -1]
		dj = [1, -1, 0, 0]
		numSearchDirs = len(di)
		(iConnected, jConnected) = ([], [])
		q = queue.Queue()
		q.put((iRoot, jRoot))
		self.__markCellAsVisited__(hasVisited, iRoot, jRoot)
		if self.__foundExit__(iRoot, jRoot, nR, nC):
			return MazeStatus.FOUND_EXIT
		while q.empty() == False:
			(u, v) = q.get()
			iConnected.append(u)
			jConnected.append(v)
			for s in range(numSearchDirs):
				iNew = u + di[s]
				jNew = v + dj[s]
				if self.__inImage__(iNew, jNew, nR, nC) and self.__isDesiredCell__(img, hasVisited, iNew, jNew):
					self.__markCellAsVisited__(hasVisited, iNew, jNew)
					q.put((iNew, jNew))
					currentStatus = self.__checkMazeStatus__(img, iNew, jNew, nR, nC)
					if currentStatus != MazeStatus.CONTINUE_SEARCH:
						return currentStatus
		return MazeStatus.NO_EXIT_EXISTS

def has_exit(maze):
	m = MazeSolver(maze)
	if not m.isValidMaze():
		raise ValueError('Maze Not Valid')
	else:
		resultSolve = m.attemptSolve()
		if resultSolve == MazeStatus.FOUND_EXIT:
			return True
		elif resultSolve == MazeStatus.NO_EXIT_EXISTS:
			return False


def has_exit(maze):
	start = [[i, maze[i].find('k')] for i in range(len(maze)) if maze[i].find('k') != -1]
	if len(start) != 1:
		raise Exception('There should no be multiple Kates')
	if backtracking(maze, start[0][0], start[0][1], set()):
		return True
	return False

def backtracking(maze, y, x, explored):
	if maze[y][x] == '#':
		explored.add((y, x))
		return False
	if (y, x) in explored:
		return False
	if x in {0, len(maze[0]) - 1} or y in {0, len(maze) - 1}:
		return True
	explored.add((y, x))
	found = backtracking(maze, y - 1, x, explored) or backtracking(maze, y, x + 1, explored) or backtracking(maze, y + 1, x, explored) or backtracking(maze, y, x - 1, explored)
	return found


def has_exit(board):

	def make(i, j, visited=None):
		if not visited:
			visited = []
		if [i, j] in visited or not (0 <= i < len(board) and 0 <= j < len(board[0])) or board[i][j] == '#':
			return False
		visited.append([i, j])
		if i == 0 or j == 0 or i == len(board) - 1 or (j == len(board[0]) - 1):
			return True
		return any([make(i + 1, j, visited), make(i - 1, j, visited), make(i, j + 1, visited), make(i, j - 1, visited)])
	li = [[i, k] for (i, j) in enumerate(board) for (k, l) in enumerate(j) if l == 'k']
	if len(li) > 1:
		raise
	return make(li[0][0], li[0][1])


def has_exit(maze):

	def rec(i, j):
		if not i in range(len(maze)):
			return True
		if not j in range(len(maze[i])):
			return True
		if maze[i][j] == '#':
			return False
		maze[i][j] = '#'
		return any((rec(i + k, j + l) for k in (-1, 0, 1) for l in (-1, 0, 1) if bool(k) != bool(l)))
	pos = None
	for (i, line) in enumerate(maze):
		for (j, c) in enumerate(line):
			if c == 'k':
				if pos:
					raise Exception('There should not be multiple Kates')
				else:
					pos = (i, j)
	if not pos:
		raise Exception('There should be a Kate')
	maze = list(map(list, maze))
	return rec(*pos)


def has_exit(maze):
	(N, M) = (len(maze) + 2, len(maze[0]) + 2)
	maze = ['b' * M] + ['b' + row + 'b' for row in maze] + ['b' * M]
	q = [(i, j) for (i, row) in enumerate(maze) for (j, c) in enumerate(row) if c == 'k']
	if len(q) != 1:
		raise Exception('Wrong number of Kates')
	v = set(q)
	while q:
		(i, j) = q.pop()
		nbs = [(i + a, j + b, maze[i + a][j + b]) for a in range(-1, 2) for b in range(-1, 2) if bool(a) != bool(b)]
		for (ni, nj, nv) in nbs:
			if nv == 'b':
				return True
			if nv == '#' or (ni, nj) in v:
				continue
			q.append((ni, nj)) or v.add((ni, nj))
	return False