_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: interview

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 []            # Already at the end, do nothing
    
    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))              # data: (origin position, direction before origin, direction after origin)
                if not xx or xx==X-1 or not yy or yy==Y-1:      # Escaped!
                    q, noPath = [], False                       # reset the queue to stop it, "from the for loop"
                    break
                    
    if noPath: return []                                        # No path, no chocolate...
    
    path = []
    while pos != start:
        pos, dir, nextDir = seens[pos]
        scal = dot(dir, nextDir)                                # scalar prouct > 0  <=>  go ahead, otherwise, turn back
        prod = cross(dir, nextDir)                              # cross product > 0  <=>  turn left, otherwise, turn right
        if scal: path.append('FB' if scal < 0 else 'F')         # dot != 0 => both directions are colinear
        else:    path.append('FL' if prod > 0 else 'FR')        # orthogonal directions, take a turn
    
    return list(''.join(path)[::-1])

# Return the array of movements to execute to get out of the maze

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]
                
            # Have we escaped?
            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
                
            # Are there any more moves to be made on this path?
            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:
        #right
        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 = '^'
        
        #left
        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 = '^'

        #down
        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 = '^'

        #up
        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),[] )]    # (isEnd,symbol,pos,steps)
    
    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])

    # find the player
    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)
            #self.draw_map(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
                    #self.draw_map(self.x, self.y)
                    return key
            if self.forks:     # 如果3个方向都不行，则检查是否能回溯，如果不能则返回None
                (self.x, self.y), self.steps, self.direct = self.forks.pop()
                return self.steps
            else:
                return None


def escape(maze):
    # Have a nice sleep ;)
    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 []