Maze 3 timer 1초 memory 32MB

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

조건은 다음과 같다.

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

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

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

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

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

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

[미로판 예제]

####

####

####

####

[미로판 예제 답]

####

##.#

...#

####

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

[미로판] 100 \times 100

####################################################################################################
##XX###############X#########################X#############X###X#XX##########XX#######X#X###########
##XXX#X#X#X#X#X#XXXXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#XXX#X#XXX#X#X#X#XXX#X#X#X#X#X#
##############XXXX#X#################################X##################X##############XX###########
##XXX#X#X#X#XXX#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#
###XX##########XXX#XX####X#########################X######X#########################################
##XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#
########################XX########XX#######################X################################X#######
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#
###################################X######################################################X#########
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#
############XXX##X#X########XX############X############X#X#############X##################X#########
##X#X#X#XXXXX#XXX#X#X#X#X#XXX#X#X#X#X#X#XXX#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#
#####################################XX###XX###########XXX##############X##################X########
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#XXX#XXX#X#X#X#XXX#X#X#X#X#X#X#X#X#XXX#X#X#X#
###############X##############X#####################X#####XXX#########X####################X########
##X#X#X#X#X#X#XXX#X#X#X#X#X#XXXXX#X#X#XXX#X#X#X#X#X#X#X#X#XXX#X#X#X#X#XXX#X#X#X#X#X#XXX#XXX#X#X#X#X#
################X#############X######X###############XX###############XX############XXX#####XXXX####
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#XXX#X#XXX#X#X#X#X#X#X#X#X#X#X#XXX#X#
#########################################XX##############X########X############################XX###
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXXXX#X#X#X#X#X#XXX#X#XXXXXXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#
###########################################XX##########XXX#X#####X#X################XX##############
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXXXX#X#X#X#XXX#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#
###X#######################XX###X####X#X##X#X###########XX###X########################XX##X#########
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#XXXXX#X#X#X#XXXXXXX#X#X#X#X#X#X#X#X#X#X#X#X#XXX#XXX#X#X#X#
####XX#################################X##########XX####XXXX###########X##########X###XX####X#X#X###
#XX#XXX#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#XXX#X#X#X#XXX#X#
#X######XXX######################################XXX###################X##################X#########
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#
###################################X#X##############XX#########X#X###X####################X#########
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#
#####################X#X###X#########X#X############X#X##########################X##################
##XXX#X#X#X#X#X#X#X#X#X#X#XXX#X#XXX#X#XXX#X#X#X#X#XXXXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#
####X#####################X########X###X###########XXXX#########X###################################
##XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXXXX#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#
########X#########################X#XXX############################################X#######XXXX#####
##X#X#XXXXX#X#X#X#X#X#X#X#X#X#XXX#XXXXXXX#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#XXX#X#X#
###############################X###X################XX######XXXXX#####XX###################XXX######
#XX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#XXXXXXXXX#XXX#X#XXX#X#X#X#X#X#XXX#X#X#X#
##X#XX##################X####X###X###################X#XX#####XXXXX##########XXXX###########X#######
#XX#XXX#X#X#X#X#X#X#XXXXXXX#XXX#XXX#X#X#X#X#X#X#X#X#X#XXXXX#X#X#X#X#X#XXX#X#X#XXX#X#X#X#X#X#X#X#X#X#
#########################XX##X#XXX#X##########X#####XX##X###############X###X##X####################
##X#X#X#X#X#X#X#X#X#X#X#X#X#XXXXXXX#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#XXX#XXX#X#X#X#X#X#X#X#X#X#X#X#
############################X####X#X##########X########X############################################
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#XXX#X#X#XXX#XXXXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#
######################XX#########X########X#################X#######################################
##X#X#X#X#X#XXX#X#X#XXXXX#X#X#X#X#X#X#X#X#XXX#X#X#XXX#X#X#XXXXX#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#
#############X#X########X##################XX#######X#X#XX##XX#X#######X#X########XX############X###
##X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#XXXXXXXXXXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#
###############X####X##############X#X#############X###XX#X###X##############XX###########X######X##
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#XXXXX#XXX#X#XXX#X#X#X#X#X#X#X#X#X#X#XXX#XXX#X#
########################X############X########XXX###########X#######X####X##XX#########X###XXXXX####
##X#X#X#X#X#X#X#X#X#XXXXX#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#XXX#XXX#X#X#X#X#X#X#XXX#X#X#X#X#X#
##########X####X#####XX#######X#X###############X##############XX#X####XX##############X#########X##
##X#X#X#XXX#X#XXX#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#XXX#X#X#XXXXX#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#
#X######X########XX#################X##############X#X#######XX#########X###########################
#XX#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#
########X##################X##XXX####X############################X#################################
#XX#X#X#X#X#X#X#X#X#X#X#XXXXXXXXX#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#
##X######################XX#X###X##################X#X#######XXX##XX##X#############################
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#XXX#X#X#X#X#X#
###XX#######XX#####X##########XX####################XX##############XX#X####XXX########X#######XX###
##X#XXX#X#XXX#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXXXXXX#X#X#X#X#XXX#X#X#XXXXX#X#X#X#X#X#X#X#XXX#X#
#####X###########XX#X#XX############XXX############X##XXX#########X#X#####XXX#X########X##########X#
##X#X#X#X#X#X#X#X#X#XXXXX#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#XXXXX#X#X#X#X#X#X#X#XXX#
############XXX####XXX#############################X################X########XXXX###########X#######
##X#X#X#X#X#X#XXX#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXXXX#X#XXX#X#X#X#X#XXX#X#X#
############X#XX########XXX#####XXX##X#############################XX#X#X###X##############XX####X##
##X#X#X#X#X#XXX#X#XXX#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#XXX#X#X#X#X#X#X#X#X#XXX#
################XXX###############X#X##X#####X#######################X#X#####X###################X##
#XX#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#XXXXX#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#
#XX##############XX#X##########################XX#######X###########XX##############################
##X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#
########################################################X#XX########################################
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#XXXXXXX#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#
################################X######################X######################XX##########X#########
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#
#XX##########X#X###X##################################################X############X#X##############
#XX#X#X#X#X#XXXXX#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#XXX#X#X#X#X#
############XX######X#################X##############################X#######X#X#########XX#########
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#XXXXXXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#
##################XX##################X################XXXX##X#########################X############
##X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#
####################XX######X#X##########X##XXX###XX##XXXX#X############XX###XX######XXX##X#########
##X#X#X#X#X#X#X#X#X#XXX#X#X#XXX#X#X#X#XXXXX#XXX#X#XXX#XXX#XXX#X#X#X#X#X#XXX#X#X#X#X#X#XXXXX#X#X#X#X#
#############################################X#X###########################X##############XX#####X##
##X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#
#XXX#####################XX####X######XX####################################X##X#XX#XX##############
#XX#X#X#X#X#X#X#X#XXX#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXXXX#X#X#X#X#X#X#
#X################X#X###################X###########################X#####X###X##XXX####XX###X######
##X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#XXXXX#X#XXX#XXX#X#X#X#X#X#
########XX##############################X##XX###########X##X#########X####XX############X###########
##X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#
########################X##############XX########X######X###############XXX#########################
##X#X#X#X#X#X#X#X#X#X#XXXXX#X#X#X#X#X#XXX#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#XXXXX#X#X#X#X#X#X#X#X#X#X#X#
#####################X##X#######################XXX#############X#X#######XX########################
##X#X#X#X#X#X#X#XXX#XXX#XXX#X#X#X#X#X#X#XXX#X#X#XXXXX#XXX#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#
################XX#XX#########X#########XXX#######X##X#XX#################################XX##XX####
##X#X#X#X#X#X#XXX#X#X#X#X#X#XXX#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#X#XXX#X#
####################################################################################################