Ruby

def maze_runner(size = 5)
  maze = size.times.map { gets.split.map {|n| [1,2,4,8].select {|e| n.to_i & e > 0} } }
  start, goals, range = [0, 0], [[size-1, size], [size, size-1]], (0...size)
  compass = ->r,c { maze[r][c].map {|k| {1 => [r,c+1], 2 => [r,c-1], 
                                         4 => [r+1,c], 8 => [r-1,c]}.assoc(k) } } 
  ways = ->path { compass[*path.keys.last].reject {|_,passed| path[passed] }. 
                    map {|dir,pt| path.merge(path.keys.last => dir, pt => 0) } }
  move = ->path { goals.index(path.keys.last) ? path : path.any? ? ways[path].flat_map(&move) : {} }
  exit = move[{start => 0}].pop
  puts (exit ? range.map {|r| range.map {|c| exit[[r,c]] || 0}.join(" ") } : "no exit")
end

Test

maze1 = " 4  5  7  3  6\n" + 
        "12  8 12  5 10\n" + 
        " 9  3 10 12  4\n" + 
        " 4  5  6  9 14\n" + 
        " 9 10  9  3 10\n"
$stdin = StringIO.new(maze1)
expect { maze_runner }.to output("no exit\n").to_stdout

maze2 = " 4  5  7  3  6\n" + 
        "12  8 12  5 10\n" + 
        " 9  3 10 12  4\n" + 
        " 4  5  6  9 14\n" + 
        " 9 10  9  3 11\n"        
$stdin = StringIO.new(maze2)
expect { maze_runner }.to output( "4 0 1 1 4\n" +
                                  "4 0 8 4 2\n" +
                                  "1 1 8 4 0\n" +
                                  "0 0 0 1 4\n" +
                                  "0 0 0 0 1\n").to_stdout

def maze_escape():
  dr = ((0,1), (0,-1), (1,0), (-1,0))
  stc = [_solver(0, 0)]
  route = [(0,0)]
  while stc:
    try:
      dx, dy, x, y = *dr[next(stc[-1])], *route[-1]
      if (x+dx, y+dy) in route: continue
      if not(0<= x+dx <len(board) and 0<= y+dy <len(board[0])): break
      stc.append(_solver(x+dx, y+dy))
      route.append((x+dx, y+dy))
    except:
      stc.pop()
      route.pop()

  for i in range(len(board)):
    for j in range(len(board[i])):
      if (i,j) not in route: board[i][j] = 0
    print(str(board[i])[1:-1].replace(',', ''))

def _solver(x, y):
  tmp = bin(board[x][y])[2:][::-1]
  for i,j in enumerate(tmp):
    if j == '1': 
      board[x][y] = 2**i
      yield i
  board[x][y] = 0



test = '''\
  4  5  7  3  6
 12  8 12  5 10
  9  3 10 12  4
  4  5  6  9 14
  9 10  9  3 11'''

board = [[*map(int, i.split())] for i in test.splitlines()]
maze_escape()

package bamin_pretest;
import java.util.Scanner;
import java.util.Arrays;
public class main {
    public static void main(String[] args) {
        int x_size = 5, y_size = 5;
        Scanner scanner = new Scanner(System.in);
        int maze[] = new int[x_size*y_size];
        for(int i = 0; i<x_size*y_size; i++)
            maze[i] = scanner.nextInt();
        int sol[] = new int[x_size*y_size];
        Arrays.fill(sol, 0);
        int position = 0;
        if (check(maze,sol,position,0)) {
            for(int i = 0; i<sol.length;i++) {
                if(i%5==0 && i!=0) System.out.println();
                System.out.print(" " + String.valueOf(sol[i]));
            }
        }
        else System.out.println("isn't solution");
    }
    public static boolean check(int[] maze, int[] sol, int position, int from) {
        if(position == maze.length-1) {sol[position] = 1; return true;}
        int temp = maze[position] - from;
        if((temp&1) != 0) {
            if(check(maze,sol,position+1,2)) {
                sol[position] = 1;
                return true;
            }
            else return false;
        }
        if((temp&2) != 0) {
            if(check(maze,sol,position-1,1)) {
                sol[position] = 2;
                return true;
            }
            else return false;
        }
        if((temp&4) != 0) {
            if(check(maze,sol,position+5,8)) {
                sol[position] = 4;
                return true;
            }
            else return false;
        }
        if((temp&8) != 0) {
            if(check(maze,sol,position-5,4)) {
                sol[position] = 8;
                return true;
            }
            else return false;
        }
        return false;
    }
}

입력란에 x_size와 y_size를 따로 받지 않기에 임의적으로 5라는 값을 직접 넣어놨습니다.

Haskell

크기가 s인 미로에서 상하좌우 이동은 일차원 배열 int maze[s*s] 에서 index가 1, -1, s, -s만큼 변하는 것으로 생각할 수 있습니다.

import Data.List
import Data.List.Split
import Control.Monad
import Control.Monad.Loops

s = 5

doors = fmap ([1,-1,s,-s]!!) . findIndices odd . take 4 . iterate (`div` 2)
solution maze = reverse $ head $ iterateUntilM ((>s*s-1) . head) advance [0]
    where advance = filter (notElem <$> head <*> tail) . (\(x:xs) -> (:x:xs) . (+x) <$> doors (maze !! x))
direction path = maybe 0 (2^) . (flip lookup dic >=> flip elemIndex [1,-1,s,-s]) <$> [0..s*s-1]
    where dic = flip zip =<< zipWith (-) =<< tail $ path
main = fmap read . words <$> getContents >>= putStrLn . unlines . fmap unwords . chunksOf 5 . fmap show . direction . solution

$ cat input | runhaskell solution
4 0 1 1 4
4 0 8 4 2
1 1 8 4 0
0 0 0 1 4
0 0 0 0 1

약간 더 읽기 편한 버전입니다.

import Data.List
import Data.List.Split
import Control.Monad
import Control.Monad.Loops

type Location = Int
type Direction = Int
type Maze = [Direction]
type Path = [Location]

delta s = [1, -1, s, -s]

solution :: Int -> Maze -> [Path]
solution s maze = reverse <$> iterateUntilM ((> s*s-1) . head) advance [0]
    where
        advance :: Path -> [Path]
        advance p = fmap (:p) $ filter (`notElem` p) $ branch $ head p

        branch :: Location -> [Location]
        branch l = (+ l) <$> (fmap ((delta s)!!) . bits $ maze !! l)

        bits :: Direction -> [Int]
        bits = findIndices odd . take 4 . iterate (`div` 2)

display :: Int -> Path -> String
display s path = unlines . fmap unwords . chunksOf s . fmap show $ dir <$> [0..s*s-1]
    where
        diff :: Location -> Maybe Int
        diff = flip lookup $ flip zip =<< zipWith (-) =<< tail $ path

        dir :: Location -> Int
        dir = maybe 0 (2^) . (diff >=> flip elemIndex (delta s))


parse :: String -> Maze
parse = fmap read . words

main = parse <$> getContents >>= mapM_ (putStrLn . display 5) . solution 5

Store Comonad와 Tree를 사용하여 만들어보았습니다.

시작점에서부터의 경로를 트리로 만들고 DFS로 미로 밖의 leaf를 찾습니다. lazy 언어이기 때문에 트리를 한꺼번에 계산하지는 않습니다.

결과적인 알고리즘은 위의 코드와 크게 다르지 않을 것 같습니다.

{-# LANGUAGE ScopedTypeVariables, ParallelListComp, DeriveFunctor, TypeSynonymInstances, FlexibleInstances #-}

import Data.List
import Data.List.Split
import Control.Monad
import Control.Monad.Loops
import Control.Comonad.Store
import Data.Fix
import Data.Bits
import Data.Ix
import Data.Maybe
import Data.Set (Set)
import qualified Data.Set as Set

import qualified Data.Map as Map

import Debug.Trace
type Loc = Int
type Dir = Int
type Maze = Store Loc Dir
type Path = [Loc]

type Seed = (Maze, Set Loc)

data TreeF a = NodeF Maze [a] deriving Functor
type Tree = Fix TreeF

escaped :: Int -> Maze -> Bool
escaped s = not . inRange (0, s*s-1) . pos

coalgebra :: Int -> Seed -> TreeF Seed
coalgebra s (maze, visited) = NodeF maze branches
  where 
    branches = if escaped s maze then [] else
      [ (seek newloc maze, Set.insert newloc visited)
      | (delta, bit) <- zip [1, -1, s, -s]
                          $ testBit (extract maze) <$> [0..3]
      , bit == True
      , let newloc = (pos maze) + delta
      , newloc `Set.notMember` visited
      ]

type Algebra f a = f a -> a

algebra :: Int -> Algebra TreeF (Loc, Maybe [(Loc, Dir)])
algebra s (NodeF maze []) = (pos maze, path)
  where
    path
      = if escaped s maze
          then Just []
          else Nothing

algebra s (NodeF maze paths) = (pos maze, path)
  where
    path
      = fmap (\(loc, Just p) -> (pos maze, toDir (pos maze - loc)) : p)
      $ find (isJust . snd)
      $ paths
    toDir = fromJust . flip elemIndex [0, 1, -1, s, -s]

solution s maze = snd $ hylo (algebra s) (coalgebra s) (maze, Set.empty)

render :: Int -> Maybe [(Loc, Dir)] -> String
render s (Just path)
  = unlines . fmap unwords . chunksOf s 
  $ [ maybe "0" show $ Map.lookup i pathMap
    | i <- [0..s*s-1]
    ]
  where
    pathMap = Map.fromList path

parse :: String -> Maze
parse str = store (map!!) 0
  where map = fmap read $ words str

main = parse <$> getContents >>= putStrLn . render 5 . solution 5

package test;

import java.util.Stack;

public class java1 {

    static int NONE  = 0;
    static int RIGHT = 1;
    static int LEFT  = 2;
    static int DOWN  = 4;
    static int UP    = 8;

    public static void main(String args[]){

        int maze[][] = {{4,5,7,3,6}
                       ,{12,8,12,5,10}
                       ,{9,3,10,12,4}
                       ,{4,5,6,9,14}
                       ,{9,10,9,3,11}};

        int loc[] = {0,0};
        Stack<Integer> route = new Stack<Integer>();
        findRoute(maze,loc,route);
    }

    /*정답 여부 판별*/
    public static boolean isFinished(int loc[]){
        boolean result = false;
        if(loc[0] < 0 || loc[0] > 4 || loc[1] < 0 || loc[1] > 4)
            result = true;
        return result;  
    }

    /*현재위치에서 이동방향에 따라 다음 위치 계산*/
    public static int[] nextLoc(int loc[], int move){       
        int[] result = new int[2];
        result[0] = loc[0];
        result[1] = loc[1];
        if(move == UP){
            result[0] = loc[0] - 1;
        }   

        if(move == DOWN){
            result[0] = loc[0] + 1;
        }

        if(move == LEFT){           
            result[1] = loc[1] - 1;
        }

        if(move == RIGHT){          
            result[1] = loc[1] + 1;
        }   

        return result;      
    }
    /* 정답 출력 */
    public static void printRoute(Stack<Integer> route){
        int[][] result =  {{0,0,0,0,0}
                          ,{0,0,0,0,0}
                          ,{0,0,0,0,0}
                          ,{0,0,0,0,0}
                          ,{0,0,0,0,0}};

        int[] loc = {0,0};
        int move = 0;
        for(int i = 0; i < route.size(); i++){
            move = route.get(i);
            result[loc[0]][loc[1]] = move;
            loc = nextLoc(loc, move);
        }


        for(int i = 0;i<5;i++){
            for(int j=0;j<5;j++){
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }

    }
    /*경로 계산*/
    public static void findRoute(int maze[][],int loc[],Stack<Integer> route){

        if(isFinished(loc)){            
            printRoute(route);
            return;
        }

        int way = maze[loc[0]][loc[1]];
        int beforeMove = NONE;

        if(route.size() != 0){
            beforeMove = route.get(route.size()-1);         
        }
        /* 이동 가능한 경로에 대해 재귀 호출(이전 위치 제외) */
        if((way & DOWN) != 0 && beforeMove != UP){          
            route.push(DOWN);
            findRoute(maze,nextLoc(loc,DOWN),route);            
        }
        if((way & RIGHT) != 0 && beforeMove != LEFT){           
            route.push(RIGHT);
            findRoute(maze,nextLoc(loc,RIGHT),route);
        }
        if((way & UP) != 0 && beforeMove != DOWN){          
            route.push(UP);
            findRoute(maze,nextLoc(loc,UP),route);          
        }   
        if((way & LEFT) != 0 && beforeMove != RIGHT){           
            route.push(LEFT);
            findRoute(maze,nextLoc(loc,LEFT),route);            
        }

        return;

    }
}

inputMaze = '''
  4  5  7  3  6
 12  8 12  5 10
  9  3 10 12  4
  4  5  6  9 14
  9 10  9  3 11
'''

maze = list()
for line in inputMaze.split('\n'):
    if line.strip() == '': continue
    toks = [int(tok) for tok in line.strip().split(' ') if tok != '']
    maze.append(toks)

for i in range(0,len(maze)):
    for j in range(i,len(maze[i])):
        tmp = maze[i][j]
        maze[i][j] = maze[j][i]
        maze[j][i] = tmp

def getInfo(secondPropositionInfo):
    directionCandidate = list()
    if (secondPropositionInfo >> 0) % 2 == 1: directionCandidate.append(2 ** 0)
    if (secondPropositionInfo >> 1) % 2 == 1: directionCandidate.append(2 ** 1)
    if (secondPropositionInfo >> 2) % 2 == 1: directionCandidate.append(2 ** 2)
    if (secondPropositionInfo >> 3) % 2 == 1: directionCandidate.append(2 ** 3)
    if (secondPropositionInfo >> 4) % 2 == 1: directionCandidate.append(2 ** 4)
    return directionCandidate

outputMaze = [ [ 0 for i in range(0,len(maze[0]))] for i in range(0,len(maze)) ]

def goMaze(x,y,x_1,y_1,before):
    outputMaze[x_1][y_1] = before
    if x>4 or y >4: return True
    for direction in getInfo(maze[x][y]):
        if direction == 1 :
            nextX= x + 1
            nextY= y
            if nextX == x_1 and nextY == y_1: continue
            if goMaze(nextX,nextY,x,y,1): return True
        if direction == 2 :
            nextX= x - 1
            nextY= y
            if nextX == x_1 and nextY == y_1: continue
            if goMaze(nextX,nextY,x,y,2): return True
        if direction == 4 :
            nextX= x 
            nextY= y + 1
            if nextX == x_1 and nextY == y_1: continue
            if goMaze(nextX,nextY,x,y,4): return True
        if direction == 8 :
            nextX= x
            nextY= y - 1
            if nextX == x_1 and nextY == y_1: continue
            if goMaze(nextX,nextY,x,y,8): return True
    outputMaze[nextX][nextY] = direction
    return False

for i in range(0,len(outputMaze)):
    for j in range(i,len(outputMaze[i])):
        tmp = outputMaze[i][j]
        outputMaze[i][j] = outputMaze[j][i]
        outputMaze[j][i] = tmp
outputMaze

import numpy as np

# custum module. Usage:
# A(1,1) + A(2,2) => A(3,3)
# A(x,y) < A(X,Y) => 0<=x<X and 0<=y<Y
from exttuple import ArrayIndex2D as A


# 7 = 1 + 2 + 4 => [(0, 1), (0, -1), (1, 0)]
def dir(d):
    info = {1:(0, 1), 2:(0, -1), 4:(1, 0), 8:(-1, 0)}
    return [info[k] for k in info if int(d) & k]


# (0, 1) => 1, (0, -1) => 2, ...
def rdir(d):
    info = {1:(0, 1), 2:(0, -1), 4:(1, 0), 8:(-1, 0)}
    rinfo = {v:k for k, v in info.items()}
    return rinfo[d]


# Q, V = queue[(pos, path[])], visited[pos]. 큐에 탈출경로를 같이 저장한다.
def escape_path(arr, X, Y):
    Q, V = [(A(0, 0), [])], set()
    while Q:
        cur, path = Q.pop(0)
        for d in dir(arr[cur]):
            next = cur + d
            if next == (X-1, Y): #탈출
                return print_path(path + [(cur, rdir(d))], X, Y)
            elif next < (X, Y) and next not in V:
                V.add(next)
                Q.append((next, path + [(cur, rdir(d))]))


# 탈출경로를 배열에 표시한다.
def print_path(path, X, Y):
    res = np.zeros((X, Y), dtype=np.int32)
    for pos, d in path:
        res[pos] = d

    return res


inp_str = '''  4  5  7  3  6
 12  8 12  5 10
  9  3 10 12  4
  4  5  6  9 14
  9 10  9  3 11'''

X, Y = 5, 5
res = escape_path(np.array(inp_str.split()).reshape((X, Y)), X, Y)
print(res)