_That's terrible! Some evil korrigans have abducted you during your sleep and threw you into a maze of thorns in the scrubland D:  
But have no worry, as long as you're asleep your mind is floating freely in the sky above your body._
> **Seeing the whole maze from above in your sleep, can you remember the list of movements you'll have to do to get out when you awake?**

---


**Input**
---
---

You are given the whole maze `maze` as a 2D grid, more specifically in your language:
```if:ruby,javascript,python
an array of strings
```
```if:java
a `char[][]`
```
```if:ruby,javascript,python,java
`maze[0][0]` is the top left-hand corner
```
```if:c
a `Maze*` (a struct with three fields: `unsigned height`, `unsigned width`, `char **grid`)
Each line is '\0' terminated, but the array of lines is not.  
`maze->grid[0][0]` is the top left-hand corner.
```
```if:java,javascript,ruby
`maze[maze.length - 1][maze[0].length - 1]` is the bottom right-hand corner
```
```if:python
`maze[len(maze) - 1][len(maze[0]) - 1]` is the bottom right-hand corner
```
```if:c
`maze->grid[maze->height - 1][maze->width - 1]` is the bottom right-hand corner.
```
Inside this 2D grid:
 - `' '` is some walkable space  
 - `'#'` is a thorn bush (you can't pass through)  
 - `'^'`, `'<'`, `'v'` or `'>'` is your sleeping body facing respectively the top, left, bottom or right side of the map.
 
---


**Output**
---
---
Write the function `escape` that returns the list/array of moves you need to do relatively to the direction you're facing in order to escape the maze (you won't be able to see the map when you wake up). as an array of the following instructions:  
 - `'F'` move one step forward  
 - `'L'` turn left  
 - `'R'` turn right  
 - `'B'` turn back   
 > Note: `'L'`,`'R'`, and `'B'` **ONLY** perform a rotation and will not move your body
 
```if:javascript,ruby,python,java
If the maze has no exit, return an empty array.
```
```if:c
If the maze has no exit, return `NULL`.
```
* This is a real maze, there is no "escape" point. Just reach the edge of the map and you're free!
* You don't explicitely HAVE to find the shortest possible route, but you're quite likely to timeout if you don't **;P**
* Aside from having no escape route the mazes will all be valid (they all contain one and only one "body" character and no other characters than the body, `"#"` and `" "`. Besides, the map will always be rectangular, you don't have to check that either)

Difficulty: MEDIUM
Tags: Fundamentals

Starter code:
def escape(maze):
	

Solutions:
from collections import deque
from numpy import cross, dot
MOVES = ((1, 0), (-1, 0), (0, 1), (0, -1))
DIRS = ('v', '^', '>', '<')

def escape(maze):
	start = (x, y) = next(((x, y) for (x, row) in enumerate(maze) for (y, c) in enumerate(row) if c not in '# '))
	(X, Y, dir) = (len(maze), len(maze[0]), MOVES[DIRS.index(maze[x][y])])
	(q, seens) = (deque([(start, dir)]), {})
	if not x or x == X - 1 or (not y) or (y == Y - 1):
		return []
	noPath = True
	while q:
		((x, y), dir) = q.popleft()
		for (dx, dy) in MOVES:
			(xx, yy) = pos = (x + dx, y + dy)
			if 0 <= xx < X and 0 <= yy < Y and (maze[xx][yy] == ' ') and (pos not in seens):
				q.append((pos, (dx, dy)))
				seens[pos] = ((x, y), dir, (dx, dy))
				if not xx or xx == X - 1 or (not yy) or (yy == Y - 1):
					(q, noPath) = ([], False)
					break
	if noPath:
		return []
	path = []
	while pos != start:
		(pos, dir, nextDir) = seens[pos]
		scal = dot(dir, nextDir)
		prod = cross(dir, nextDir)
		if scal:
			path.append('FB' if scal < 0 else 'F')
		else:
			path.append('FL' if prod > 0 else 'FR')
	return list(''.join(path)[::-1])


def first_position(maze):
	for i in range(len(maze)):
		for j in range(len(maze[0])):
			if maze[i][j] in '><^v':
				return (i, j)

def walking(maze, passed, path, x, y, move):
	(lin, col) = (len(maze), len(maze[0]))
	if x < 0 or x >= lin or y < 0 or (y >= col):
		return True
	if maze[x][y] == '#' or passed[x][y]:
		return False
	passed[x][y] = True
	if move == '>':
		r = walking(maze, passed, path, x + 1, y, 'v')
		l = walking(maze, passed, path, x - 1, y, '^')
		f = walking(maze, passed, path, x, y + 1, '>')
		b = walking(maze, passed, path, x, y - 1, '<')
	elif move == '<':
		r = walking(maze, passed, path, x - 1, y, '^')
		l = walking(maze, passed, path, x + 1, y, 'v')
		f = walking(maze, passed, path, x, y - 1, '<')
		b = walking(maze, passed, path, x, y + 1, '>')
	elif move == '^':
		r = walking(maze, passed, path, x, y + 1, '>')
		l = walking(maze, passed, path, x, y - 1, '<')
		b = walking(maze, passed, path, x + 1, y, 'v')
		f = walking(maze, passed, path, x - 1, y, '^')
	elif move == 'v':
		r = walking(maze, passed, path, x, y - 1, '<')
		l = walking(maze, passed, path, x, y + 1, '>')
		b = walking(maze, passed, path, x - 1, y, '^')
		f = walking(maze, passed, path, x + 1, y, 'v')
	if f:
		path += ['F']
	elif b:
		path += ['F', 'B']
	elif r:
		path += ['F', 'R']
	elif l:
		path += ['F', 'L']
	return f or b or r or l

def escape(maze):
	path = []
	passed = [[False for j in range(len(maze[0]))] for i in range(len(maze))]
	(i, j) = first_position(maze)
	walking(maze, passed, path, i, j, maze[i][j])
	return path[::-1]


D = {(0, 1): {(-1, 0): 'L', (1, 0): 'R', (0, -1): 'B'}, (1, 0): {(0, 1): 'L', (0, -1): 'R', (-1, 0): 'B'}, (0, -1): {(1, 0): 'L', (-1, 0): 'R', (0, 1): 'B'}, (-1, 0): {(0, -1): 'L', (0, 1): 'R', (1, 0): 'B'}}

def escape(maze):
	P = {(r, c) for (r, row) in enumerate(maze) for (c, v) in enumerate(row) if v == ' '}
	paths = [[{(r, c) for (r, row) in enumerate(maze) for (c, v) in enumerate(row) if v in '<>^v'}.pop()]]
	faces = {'v': (1, 0), '^': (-1, 0), '<': (0, -1), '>': (0, 1)}[{c for r in maze for c in r if c in '<>^v'}.pop()]
	while paths:
		newp = []
		for path in paths:
			(r, c) = path[-1]
			if r * c == 0 or r == len(maze) - 1 or c == len(maze[0]) - 1:
				moves = []
				for p in [(b[0] - a[0], b[1] - a[1]) for (a, b) in zip(path, path[1:])]:
					moves += ([D[faces][p]] if faces != p else []) + ['F']
					faces = p
				return moves
			for p in {(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)} & P:
				newp.append(path + [p])
				P.remove(p)
		paths = newp
	return []


from collections import deque
MOVES = {(-1, 0): 'up', (1, 0): 'down', (0, -1): 'left', (0, 1): 'right'}
STATES = ('<', '>', '^', 'v')

def find_start(m):
	for row in range(len(m)):
		for col in range(len(m[row])):
			if m[row][col] in STATES:
				return ((row, col), m[row][col])

def escape(maze):
	stored_path = {}
	maze = [list(x) for x in maze]
	row = len(maze)
	col = len(maze[0])
	(start, state) = find_start(maze)
	end = []
	queue = deque([start])
	while queue:
		(x, y) = queue.popleft()
		for (dx, dy) in list(MOVES.keys()):
			xx = x + dx
			yy = y + dy
			if 0 <= xx < row and 0 <= yy < col and (maze[xx][yy] != '#'):
				queue.append((xx, yy))
				stored_path[xx, yy] = (x, y)
				if (xx == 0 or xx == row - 1) and maze[xx][yy] or (yy == 0 or (yy == col - 1 and maze[xx][yy])):
					end = (xx, yy)
					break
				maze[xx][yy] = '#'
	if not end:
		return end
	full_path = []
	pos = end
	while pos != start:
		(x1, y1) = pos
		pos = stored_path[pos]
		(x2, y2) = pos
		full_path.append(MOVES[x1 - x2, y1 - y2])
	PATH = full_path[::-1]
	out = []
	for direction in PATH:
		if state == '>' and direction == 'down':
			out.append('R')
			out.append('F')
			state = 'v'
		elif state == '>' and direction == 'right':
			out.append('F')
		elif state == '>' and direction == 'left':
			out.append('B')
			out.append('F')
			state = '<'
		elif state == '>' and direction == 'up':
			out.append('L')
			out.append('F')
			state = '^'
		elif state == '<' and direction == 'down':
			out.append('L')
			out.append('F')
			state = 'v'
		elif state == '<' and direction == 'left':
			out.append('F')
		elif state == '<' and direction == 'right':
			out.append('B')
			out.append('F')
			state = '>'
		elif state == '<' and direction == 'up':
			out.append('R')
			out.append('F')
			state = '^'
		elif state == 'v' and direction == 'down':
			out.append('F')
			state = 'v'
		elif state == 'v' and direction == 'left':
			out.append('R')
			out.append('F')
			state = '<'
		elif state == 'v' and direction == 'right':
			out.append('L')
			out.append('F')
			state = '>'
		elif state == 'v' and direction == 'up':
			out.append('B')
			out.append('F')
			state = '^'
		elif state == '^' and direction == 'down':
			out.append('B')
			out.append('F')
			state = 'v'
		elif state == '^' and direction == 'left':
			out.append('L')
			out.append('F')
			state = '<'
		elif state == '^' and direction == 'right':
			out.append('R')
			out.append('F')
			state = '>'
		elif state == '^' and direction == 'up':
			out.append('F')
	return out


from heapq import *

def escape(maze):
	MOVES = {(-1, 0): '^', (1, 0): 'v', (0, -1): '<', (0, 1): '>'}
	direc = {('v^', '^v', '<>', '><'): 'B', ('^<', 'v>', '>^', '<v'): 'L', ('^>', '>v', '<^', 'v<'): 'R'}
	maze = '\n'.join(maze)
	maze = list(map(list, maze.split('\n')))
	(X, Y) = (len(maze) - 1, len(maze[0]) - 1)
	for i in range(X + 1):
		for j in ('^', '<', 'v', '>'):
			if j in maze[i]:
				sym = j
				row = i
	(x, y) = (row, maze[row].index(sym))
	xend = (0, X)
	yend = (0, Y)
	q = [(0, sym, (x, y), [])]
	while q and (not q[0][0]):
		(_, sym, (x, y), S) = heappop(q)
		for (dx, dy) in MOVES:
			pos = (a, b) = (x + dx, y + dy)
			if 0 <= a <= X and 0 <= b <= Y and (maze[a][b] != '#'):
				maze[a][b] = '#'
				steps = S.copy()
				for i in direc:
					if sym + MOVES[dx, dy] in i:
						steps.append(direc[i])
						break
				steps.append('F')
				heappush(q, (a in xend or b in yend, MOVES[dx, dy], pos, steps))
	return q and q[0][0] and q[0][3]


import re

def escape(maze):
	PLAYER = re.compile('[><^v]')
	MOVE = {'D': {'>': ['R', 'F'], '<': ['L', 'F'], '^': ['B', 'F'], 'v': ['F']}, 'U': {'>': ['L', 'F'], '<': ['R', 'F'], '^': ['F'], 'v': ['B', 'F']}, 'R': {'>': ['F'], '<': ['B', 'F'], '^': ['R', 'F'], 'v': ['L', 'F']}, 'L': {'>': ['B', 'F'], '<': ['F'], '^': ['L', 'F'], 'v': ['R', 'F']}}
	(ymax, xmax) = (len(maze), len(maze[0]))
	for (idx, line) in enumerate(maze):
		player = PLAYER.search(line)
		if player is not None:
			(y, x) = (idx, player.start())
			stack = [(y, x, maze[y][x], [])]
			break
	s = set()
	while len(stack) != 0:
		(y, x, pos, moves) = stack.pop(0)
		if y == 0 or x == 0 or y == ymax - 1 or (x == xmax - 1):
			return moves
		if (y, x) in s:
			continue
		s.add((y, x))
		if y + 1 < ymax and maze[y + 1][x] == ' ':
			stack.append((y + 1, x, 'v', moves + MOVE['D'][pos]))
		if y - 1 >= 0 and maze[y - 1][x] == ' ':
			stack.append((y - 1, x, '^', moves + MOVE['U'][pos]))
		if x + 1 < xmax and maze[y][x + 1] == ' ':
			stack.append((y, x + 1, '>', moves + MOVE['R'][pos]))
		if x - 1 >= 0 and maze[y][x - 1] == ' ':
			stack.append((y, x - 1, '<', moves + MOVE['L'][pos]))
	return []


class Piece:

	def __init__(self, map):
		self.map = map
		self.size = (len(map) - 1, len(map[0]) - 1)
		for (num, line) in enumerate(map):
			for tag in ('^', '<', 'v', '>'):
				if tag in line:
					(self.x, self.y, self.direct) = (num, line.index(tag), tag)
		self.walked = set()
		self.walked.add((self.x, self.y))
		self.forks = []
		self.steps = 0
		self.check_fork(self.x, self.y, 1)
		self.dir = {'up': ('^', (-1, 0)), 'down': ('v', (1, 0)), 'left': ('<', (0, -1)), 'right': ('>', (0, 1))}
		self.turn = {'>': {'L': self.dir['up'], 'R': self.dir['down'], 'B': self.dir['left'], 'F': self.dir['right']}, '<': {'L': self.dir['down'], 'R': self.dir['up'], 'B': self.dir['right'], 'F': self.dir['left']}, '^': {'L': self.dir['left'], 'R': self.dir['right'], 'B': self.dir['down'], 'F': self.dir['up']}, 'v': {'L': self.dir['right'], 'R': self.dir['left'], 'B': self.dir['up'], 'F': self.dir['down']}}

	def check_fork(self, x, y, direct=2):
		count = 0
		for (x_, y_) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
			if x_ >= 0 and x_ <= self.size[0] and (y_ >= 0) and (y_ <= self.size[1]):
				if self.map[x_][y_] != '#':
					count += 1
		fork = ((x, y), self.steps, self.direct)
		for _ in range(count - direct):
			self.forks.append(fork)

	def draw_map(self, x, y):
		self.map[x] = self.map[x][:y] + self.direct + self.map[x][y + 1:]

	def go_forward(self):
		(self.direct, (x, y)) = self.turn[self.direct]['F']
		(x, y) = (self.x + x, self.y + y)
		if self.map[x][y] != '#' and (x, y) not in self.walked:
			(self.x, self.y) = (x, y)
			self.walked.add((x, y))
			self.steps += 1
			self.check_fork(x, y)
			return 'F'
		else:
			for key in ('L', 'R', 'B'):
				(direct, (x, y)) = self.turn[self.direct][key]
				(x, y) = (self.x + x, self.y + y)
				if self.map[x][y] != '#' and (x, y) not in self.walked:
					self.direct = direct
					self.steps += 1
					return key
			if self.forks:
				((self.x, self.y), self.steps, self.direct) = self.forks.pop()
				return self.steps
			else:
				return None

def escape(maze):
	p = Piece(maze)
	res = ''
	while p.x not in (0, p.size[0]) and p.y not in (0, p.size[1]):
		tmp = p.go_forward()
		if tmp is None:
			return []
		elif isinstance(tmp, int):
			res = res[:tmp]
		else:
			res += tmp
	return list(res)


from collections import deque
B = {'^': 'v', 'v': '^', '<': '>', '>': '<'}
L = {'^': '<', 'v': '>', '<': 'v', '>': '^'}
R = {'^': '>', 'v': '<', '<': '^', '>': 'v'}
F = {'^': lambda i, j: (i - 1, j), 'v': lambda i, j: (i + 1, j), '<': lambda i, j: (i, j - 1), '>': lambda i, j: (i, j + 1)}

def escape(maze):
	(H, W) = (len(maze), len(maze[0]))
	(a, b, c) = next(((a, b, c) for (a, row) in enumerate(maze) for (b, c) in enumerate(row) if c in '^<v>'))
	(left, seen) = (deque([(a, b, c, [])]), set())
	while left:
		(i, j, p, T) = left.popleft()
		if i in (0, H - 1) or j in (0, W - 1):
			return T
		if (i, j, p) in seen:
			continue
		seen.add((i, j, p))
		(k, l) = F[p](i, j)
		if maze[k][l] == ' ':
			left.append((k, l, p, T + ['F']))
		left.extend([(i, j, L[p], T + ['L']), (i, j, R[p], T + ['R']), (i, j, B[p], T + ['B'])])
	return []


def escape(maze):
	(h, w) = (len(maze), len(maze[0]))
	maze = [list(row) for row in maze]
	(i, j, face) = find_self(maze)
	maze[i][j] = '#'
	paths = [[i, j, face, []]]
	while paths:
		(i, j, face, path) = paths.pop(0)
		if i == 0 or i + 1 == h or j == 0 or (j + 1 == w):
			return path
		for (step, mi, mj, new_face) in directions(i, j, face):
			if maze[mi][mj] != '#':
				paths.append([mi, mj, new_face, path + step])
				maze[mi][mj] = '#'
	return []

def find_self(maze):
	faces = {'^': (-1, 0), '<': (0, -1), 'v': (1, 0), '>': (0, 1)}
	for (i, row) in enumerate(maze):
		for (j, cell) in enumerate(row):
			if cell in faces:
				return (i, j, faces[cell])

def directions(i, j, face):
	(fi, fj) = face
	return [[['F'], i + fi, j + fj, face], [['L', 'F'], i - fj, j + fi, (-fj, fi)], [['R', 'F'], i + fj, j - fi, (fj, -fi)], [['B', 'F'], i - fi, j - fj, (-fi, -fj)]]


from collections import deque
derp = {'^': (-1, 0), '<': (0, -1), 'v': (+1, 0), '>': (0, +1)}

def turn(d1, d2):
	(m1, m2) = (derp[d1], derp[d2])
	if m1[0] + m2[0] == 0 and m1[1] + m2[1] == 0:
		return 'B'
	if m2[0] - m1[0] + m2[1] + m1[1] == 0:
		return 'L'
	return 'R'

def neighs(maze, pos):
	(i, j, d) = pos
	(mi, mj) = derp[d]
	(ni, nj) = (i + mi, j + mj)
	return [(ni, nj, d)] + [(i, j, nd) for nd in derp.keys() - {d}]

def escape(maze):
	pos = next(((i, j, cell) for (i, row) in enumerate(maze) for (j, cell) in enumerate(row) if cell in derp))
	q = deque([pos])
	prev = {pos: None}
	while q:
		(i, j, d) = pos = q.popleft()
		try:
			if i < 0 or j < 0:
				raise IndexError
			cell = maze[i][j]
		except IndexError:
			rpath = []
			while True:
				pp = prev[pos]
				if pp is None:
					break
				((_, _, d1), (_, _, d2)) = (pp, pos)
				if d1 == d2:
					rpath.append('F')
				else:
					rpath.append(turn(d1, d2))
				pos = pp
			return rpath[::-1]
		if cell == '#':
			continue
		for n in neighs(maze, pos):
			if n not in prev:
				(i, j, d) = n
				q.append(n)
				prev[n] = pos
	return []