Maze 4 timer 1초 memory 256MB

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

조건은 다음과 같다.

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

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

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

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

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

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

[미로판 예제]

####

####

####

####

[미로판 예제 답]

####

##.#

...#

####

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

[미로판] 100 \times 100

####################################################################################################
########X#############XXXX#XXX#XX######################################XXXX#X#XX#XX####XX#XXXXXXX##X
#XXX##X############X#XXXXX#XXXXX#######################################XXXX###X##XX###XXXX#XXXXXXX#X
#XXXXXX############XX#XXXX##XXXX######################################XXXXX#X#XX##X#####X###XXXXXXXX
#XX#####################XXX#XXXXX#####################################XXXXXXX###XXXX########XXXXXX#X
#X#XX#################XXXX#XXXXXXXX##################################XXXXXXXX######X#######XXXXXXXXX
##XX###################XXX##XXXXXXX##################################XX#XXX#################XXXX####
####XX#################XXXXXXX#XXX###################################XXXXX#################XX#X#####
#####X#################XXXXX#X#XXX##################################XX####X#########################
####XXX################XX#XXXXXXXX#X####################X##########XXX##############################
#####XXX##########X####XXXXX#XXXXXX#X##################XXX###########X###############X##############
######XXX#########XX##XXXXXXXXXXXX#X##################X#XXXX#######X#X#X##XX#X######XXX#############
#X####XX##########XX#XXXX###XXX##XXXX################X#X#XXX#######XXXX#XXXXXX#######XXX############
#XXX##XX##########X#XXX######X#X##XX##################X#XXXX#######XXXXXXX#XXX####XXX#XX############
#XX###XX##########XXXX########X#XXX#X###################XXXXX########X#XXX###X#XXXXXXXXX############
#X###XXXX##################X#XXX#XX#X################XX#XXXXXX########XXX####XXXX#XXX###############
#XXXXXXXX##################XXXXXXX#XX################XXXXXXXX##########XX#####XX#XXXXX##############
##XXXXXX#X##############XXXXXXXXX###XXX########X##XXX#XX#XXX###########XXX##XXX##XXXXX##############
###XXX####################XXXXXXX##XXX#########XXX##XXXXX##X############XX#XXXX#XXXXXXX#############
##########################XXX#XXX####XXX######XXX#XXXXXXX##X#############X#XXX#XXXXXXX##############
##############################XX######XX#######X#X##XXXXX#XXX#############X##XXXXXXXX###############
###############################X#####XXXX####X#XXX##XXXXXXX################XX#XXXXXXX###############
###############################XX####XXXX###XXXX#XXXXXXXXXXX##############XXXXXXXXXX################
############################XXXX#XX#XXXX###XXXXX#XX#XXXXXXX#############XXX#XXXXXXXX################
#############################X#X##XXXXX#####XXX####XXX#XXX#############XXXX##X#X#XX#################
##############################XXX#XXXXX#####XXXXXXX####X####################XXX#XXX#################
###############################X#X#XXXX#X###X#XXXXX########################XXX###XXX################
############################XXXXX#XXXX#X########X##########################XX#######################
###########################XXXX#X#XXX######################################XXX######################
##########################XXXXXXX#XXX#####################################XXX#######################
##########################XXXXXXXX#XXX####################################XXX#######################
##########################XXXX#XX###XXXX#################################X##########################
###########################XX##XXX#####XX###############################XXX#########################
#################################X###XXXXX#################################XX#######################
#################################X###XXXX###########################################################
################################X#X##XXXX###########################################################
##########################XX####XXXXXXXXX##X########################################################
##########################XXXXX#XX#XXXXXXXX#X#######################################################
##########################XXXXXXXXXXX#XXXX###X######################################################
##########################XXXXXX#XXX###X#X#XXX######################################################
##########################XXXXX#XXXXXX####X#XXX#####################################################
#############################X#XXXXXXXX#####XX######################################################
#XX############################XXXXXXXX####XXX######################################################
#XX#############################XX###X###XX#X#######################################################
##X#########XXX################XXXX###X#X##XXX################################################X#X###
####X#######XXXX###############XXX#####XX#XX#XXX##############################################XX#X##
#XXXX#####XXXXXX################X########XXXX#XX##X#############################################XXXX
#XXXXX###XXXXXXXX####################XX#X#XX##XX##XX###########################################XXX##
###XX##XXXXXXXXXX###################X#XXX##X#X#XXXX############################################XX#X#
#XXX#X#XXXXX#XXXXX########XXX######X#####XXXXXX################################################XXX##
#XXXX#XXX#XX#XXXXXXXX####XXXXXX####X####XXXXX#################################################XXXXXX
#X#XXX###XXX###XXXXXX###XXXXXXX#X###X#X#XXX###########X#######################################XXXXXX
#XXXXX####X#####XX#X##XXXXXXXXXXX###XXXX#############X#X#XX##################################XXX#XXX
#XXXX##########XXXX###XXXXXXXXX####XX##X##############XXXXX#X################################XX####X
#XXX#############XXX#XXXXXXX######XX###################XXXXXX#################################X#XXXX
#XX##############XX###XXXXXX###########################XXX#XXX#################################XXXX#
#XXX###################XXXXX##############################X##################################XXXXXXX
#XX#####################X#XX#############################X#################X################XXXXXX#X
##X#####################XX##############################X#################X#X################XXXXXX#
######################################################XXX################XXXX################XXX#XXX
########XX#############################################X###############XXXXXXX################XXXXX#
####XXXX##XX####XXX####################################X################XXXXXXX###############X#XXX#
####XX#########XXXX#####################################X###############XXX##XXX#####XXX######X#X#X#
#####X#########X#XX#####################################XX#############XXXX#XXX######XXXXX#######X##
####XXX#########X######################################X#X#############XX#XXXXXX###XX###XX##X##X##XX
##XXX#XXXX###XX#X#X#####################X############XX##XX#####X####XX##XXX###XXXXX#XX#XX#X#XXXXX##
##XX###XX###XXXXXXXX###############XXX#X#X##########X###XX######XX#X##XXX#X###X##XXXXXXXX##XXXXXX#XX
#XXX#XXXXXX#X#X#X#X################XXXX###X#########XX###X#####XXXXX#XXXXX#XXXXXXXXXXXXXXXXXXXX##X#X
#X#XXXXXXXXX#XX##XXX###############X###X#XXX####X###XXX#######X#XXXXXXXXX#XXXXXXXXXXXXXX###XX####XX#
#XXXXXXXXXXX#XXX#XX#X###############X#XX#XXXX###XXX##X#######X###XXXX#XXXXXXXXXXX###XXX#########XXXX
#X#XXXX###X#X#XXXXXXX#############XXX##XX#XX###X#X#XX########X#####XXX#XXX#XXXXX################XX##
#XXXXXXX#XXX#XXXXXXX##############XX#X##XX#XX#XXXXXXX########X######XX#XXX##XXXXXX################XX
#XXXXXXXXXXX#XX#XXXX#############XXXX###XX#XX##XXXX#X#########X#####X#X#XX#X#XXXXXX################X
#XXXXXX#XXXXXXXXXXX##############XXXXX#XXXXXX##XXX###########X#########XXXXXXXXXXXXX###############X
#XXXXXXX#X##XXXXXXX################XX######XX##XXXXX########X###XX#XXX#XXXXXXX#XXXX#################
#XXXXX###XXX##XXX################XXXXX######XX#XX#X#########XXX##XXXXXXXX#XXXXXXXX############XX####
##XXXX##XXXX###X#################XX#XX######XX#X#X#############XXXXXXXXX##XXXXXXX########X#####XXX##
##XXXX#XXXXX#####################X##########X####################X#XXXXX####XX#X########XX###XXXXX##
######XXXXX#####################XXX##############################XXXXXXX####X##XX#######XXX#XXXXX###
######X##XXX#####################XXX############################XXXXX#XX########XX#######XXXXXXXXX##
######X###X###############X#XX#####################################XXX#X#######XXX#########XXXXXX#XX
#####XX#XXX###############XXXXX####################################X#XX#######X#XX#########X##X#XX#X
####XX###XX################XX#XX####################################XXX#########################XX#X
####XX#XX#X#################XX#######################################XXX############################
#X#XXXXX#X#X################XX#######################################XXXX###########################
#XXXXXXXXXX################XX#X#####################################################################
#XXXXXXXXXX###############XXX#X#####################################################################
#XXXXXXXXX################X#X##X###################################################################X
#XXXXXXXX#################X###X####################################################################X
#X#XXXX#XX###############XX########################################################################X
##X#XXXXX################XX#########################################################################
###X#XXXX################XXX########################################################################
###XXXXXX################XX#XX######################################################################
###XXXXXX################XXX#XX#####################################################################
#X#XX#XXXX################XXXXX#####################################################################
##XX###X#XX################XXXXX####################################################################
##########################XXXXXX###XXX########################XXXX##############################X###
##########################XXXXX###XXX#XX###################X#XXXX#X###########################XX#XX#
###########################XX#####X#XXX###################XXXXXXXXXXXXX##X#################X##X#X##X
###########################XX#X#XXXXXXX####################XXXXXXXXXX##XXX######X##########XXXXXXXX#