Maze 8 timer 1초 memory 256MB

아래 주어진 미로에서 #을 .으로 바꾸어 미로를 만들어보자.

조건은 다음과 같다.

1. X는 바꿀 수도 이동할 수도 없는 곳이다.

2. 가장자리는 단 한 곳만 길이 뚫려있다.

3. 길은 상하좌우로만 이동이 가능하다.

4. 길은 무조건 하나의 경로만이 존재한다.

우리의 목적은 최대한 길을 길게 만드는 것이다.

예를 들어 아래와 같은 미로판이 주어지면 답은 이와 같다.

[미로판 예제]

####

####

####

####

[미로판 예제 답]

####

##.#

...#

####

우리가 완성해야 하는 미로판은 아래와 같다.

[미로판] 20 \times 20

X#X########XX#XXXXX#
#XX#######XX###X#XXX
X#XX#XX############X
X#XX#XX#############
####XX#############X
X####X####XXX######X
###X#X####XXX####X#X
X#XXXX#X##XXX#X#XXX#
##XXXXX#XX###XXXXXXX
###XXX#XXXX##XXX####
########XX####XX####
########XX#####XX###
#########X#####XX###
####XX##############
####XXX#############
#####XX#############
######XX############
X#####X########XX##X
XX##########XX#XX#X#
X###########XXXXXXXX