Создание лабиринтов картинок

20

Вызов

Напишите программу / функцию, которая принимает «изображение» и выводит лабиринт изображения, сформированный из этого изображения.

вход

Ваша программа должна принимать два аргумента:

  • Я, образ, чтобы сформировать лабиринт из
  • S, логическое значение, указывающее, отображать или нет решение для лабиринта

Мне дается в следующем виде:

.......
.#####.
.#####.
#######
.#####.
.#####.
.......

где #s - ячейки, которые должны быть включены в путь решения, а .s - ячейки, которые должны быть исключены. Вы можете поменять местами буквы .«s», #«s» и «newline» с любым персонажем по вашему выбору, если они отличаются друг от друга. В качестве альтернативы вы можете принять фактическое растровое изображение входного изображения.

Выход

Ваш получающийся лабиринт должен быть в следующей форме:

###############
#             #
# ### ####### #
# #.........# #
# #.#######.# #
# #.#.......# #
###.#.#########
....#.#........
#####.#.#######
#  ...#.....  #
# #.#######.# #
# #.........# #
# ####### ### #
#   #       # #
###############

где #s обозначает стены, .s обозначает части пути, которые являются частью решения, а пробелы являются путями, исключенными из решения. В .«s могут быть заменены пробелами , если S ложно. Опять же, символы могут быть заменены другими символами по вашему выбору, или вы можете вывести фактическое растровое изображение лабиринта с выделенным решением.

дополнительные детали

  • Пути должны быть шириной в одну ячейку (путь не может иметь гигантский пул пустого пространства)
  • Лабиринт не должен содержать петель
  • Лабиринт должен быть полностью соединен (все ячейки должны быть доступны от входа / выхода)
  • Лабиринт должен быть окружен стенами (если только не вход / выход)
  • Путь решения не должен включать тупики
  • В лабиринте должно быть ровно 1 вход и 1 выход
  • Вход и выход должны быть выровнены по краю сетки и прилегать к ячейке, включенной в путь решения
  • Вы можете выбрать, где находятся вход и выход
  • Вы можете предположить, что правильный путь может быть сформирован из данного входного изображения

(Добавлено для пояснения) На диаграмме ниже показано, как путь решения соотносится с входным изображением:

Input (I): |    Output:            |    Corresponding Cells: 
           |                       |    (@'s denote #'s from I)
           |                       |
.......    |    ###############    |    ###############
.#####.    |    #             #    |    #             #
.#####.    |    # ### ####### #    |    # ### ####### #
#######    |    # #.........# #    |    # #@.@.@.@.@# #
.#####.    |    # #.#######.# #    |    # #.#######.# #
.#####.    |    # #.#.......# #    |    # #@#@.@.@.@# #
.......    |    ###.#.#########    |    ###.#.#########
           |    ....#.#........    |    .@.@#@#@.@.@.@.
           |    #####.#.#######    |    #####.#.#######
           |    #  ...#.....  #    |    #  @.@#@.@.@  #
           |    # #.#######.# #    |    # #.#######.# #
           |    # #.........# #    |    # #@.@.@.@.@# #
           |    # ####### ### #    |    # ####### ### #
           |    #   #       # #    |    #   #       # #
           |    ###############    |    ###############
           |                       |

Тестовые случаи

Пример лейки из Википедии :

Входные данные:

..................
..................
.......####.......
......##..##......
.....##....##....#
.....#......#...##
.#############.##.
##..############..
#...###########...
#...##########....
#...##########....
#...##########....
#...##########....
....##########....
....##########....
....##########....
..................
..................

Выход (S = false):

#####################################
#   #     #   #   #     #           #
# ### ### ### # # ##### ### ### ### #
#     # #   # # #         # #   # # #
# ### # ##### # ########### # ### # #
# # #         #           # # #   # #
# # # ### ##### # ### ### # ### ### #
#   # # #   #   # # #   # #   # #   #
# ### # ##### ##### ### ##### # # ###
# #   #       #   #   #       # # #  
### ####### ### ### # ### ##### ### #
#   #     # #   #   #   # #   # #   #
# ### ##### # ### ####### # # # # # #
# #       #             #   # #   # #
# # ##### ############# ### ### ### #
#   #   #       #     #   # #   # # #
# ### # ####### # ### ### # # ### # #
# # # #         #   # #   #   #     #
# # # ### ######### # # ##### # #####
# #   # # #       # #   #   # # #   #
# ##### # # ##### # ##### # # ### # #
#       # #   #   # #     # #   # # #
# ### ### ### # ### # ##### ####### #
#   # # #     # #   # #       #     #
# # # # ####### # ### # ##### # ### #
  # # # #   #   #     #     # #   # #
### # # # # # ############# # ### # #
#   # # # #   #         #   # #   # #
##### # # ##### ####### # ### ##### #
#     # # #   #       # #   #       #
##### # # # # ####### # ### #########
#     #     #         #       #     #
# ### ######### ############# # #####
# # #   #     # #       #     #     #
# # ######### # ####### ####### ### #
#             #                 #   #
#####################################

Выход (S = true):

#####################################
#   #     #   #   #     #           #
# ### ### ### # # ##### ### ### ### #
#     # #   # # #         # #   # # #
# ### # ##### # ########### # ### # #
# # #         #.......    # # #   # #
# # # ### #####.# ###.### # ### ### #
#   # # #   #...# # #...# #   # #   #
# ### # #####.##### ###.##### # # ###
# #   #    ...#   #   #...    # # #..
### #######.### ### # ###.##### ###.#
#   #     #.#   #   #   #.#   # #...#
# ### #####.# ### #######.# # # #.# #
# #.......#.............#...# #...# #
# #.#####.#############.###.###.### #
#...#   #.......#.....#...#.#...# # #
#.### # #######.#.###.###.#.#.### # #
#.# # #  .......#...#.#...#...#     #
#.# # ###.#########.#.#.##### # #####
#.#   # #.#.......#.#...#...# # #   #
#.##### #.#.#####.#.#####.#.# ### # #
#.      #.#...#...#.#.....#.#   # # #
#.### ###.###.#.###.#.#####.####### #
#.  # # #.....#.#...#.#.....  #     #
#.# # # #######.#.###.#.##### # ### #
..# # # #...#...#.....#.....# #   # #
### # # #.#.#.#############.# ### # #
#   # # #.#...#.........#...# #   # #
##### # #.#####.#######.#.### ##### #
#     # #.#...#.......#.#...#       #
##### # #.#.#.#######.#.###.#########
#     #  ...#.........#.....  #     #
# ### ######### ############# # #####
# # #   #     # #       #     #     #
# # ######### # ####### ####### ### #
#             #                 #   #
#####################################

Пример растрового изображения (тот же лабиринт, что и выше):

Вход: Ввод растрового изображенияВыход (S = ложь): Выходное растровое решение не выделеноВыход (S = истина):Выходное растровое решение выделено

Dendrobium
источник
4
Это может быть только я, но я не вижу входное изображение в выходном лабиринте.
Майк Буфардечи
@ mike-bufardeci Добавлена ​​диаграмма, показывающая входное изображение в выходном лабиринте. Надеюсь, это поможет!
Дендробиум
2
Кажется, не существует правила, требующего подключения лабиринта. Будет ли это правильным решением? Также, кажется, не существует правила, что сетка должна быть окружена стенами (если только всякая стена не считается входом или выходом). Будет ли это правильным решением?
Мартин Эндер
1
Также добавьте еще несколько тестов.
Flawr
@ MartinBüttner Лабиринт должен быть полностью соединен и окружен стенами, отредактировал вопрос, разъясняющий эти моменты.
Дендробиум

Ответы:

10

Питон 3, 1599 байт

Я нашел, что это был забавный проект и очень интересный (и несколько длительный). Когда я увидел это, мне напомнили о лете, которое я провел исключительно за написанием и улучшением алгоритма создания лабиринта, и сразу же приступил к работе над этим.

Через некоторое время у меня был начальный черновик длиной около 6000 байтов, и я потратил следующие пару часов, чтобы сконцентрировать его в следующей программе:

import math,random;R=range;L=len;T=sorted;P=print;N=random.randint
def M(I,S):
 I=I.rsplit('\n');s=[0]*(1+L(I[0])*2);G=[s]
 for i in R(L(I)):
  r=[0]
  for x in I[i]:r+=x,0
  G+=[r];s=[0]*(1+L(I[0])*2);G+=[s]
 c=E(G,L(G[0])-2,-2);G[c][L(G[0])-1]=1;e=[c,L(G[0])-2];c=E(G,1,2);G[c][0]=1;G[c][1]=1;s=[c,1]
 while s!=e:
  o=[];Q(G,s,e,-2,0,o,0);Q(G,s,e,0,2,o,1);Q(G,s,e,2,0,o,2);Q(G,s,e,0,-2,o,3);o=T(o,key=lambda x:(x[2],-x[1]))[0][0]
  if o==0:G[s[0]-1][s[1]]=1;s[0]-=2
  elif o==1:G[s[0]][s[1]+1]=1;s[1]+=2
  elif o==2:G[s[0]+1][s[1]]=1;s[0]+=2
  else:G[s[0]][s[1]-1]=1;s[1]-=2
  G[s[0]][s[1]]=1
 s=0
 while not s:
  r=N(1,(L(G)-1)/2)*2-1;c=N(1,(L(G[0])-1)/2)*2-1
  if G[r][c]in[1,2]:
   o=[];F(G,r-2,c,o,0);F(G,r,c+2,o,1);F(G,r+2,c,o,2);F(G,r,c-2,o,3)
   try:
    if o[0]==0:G[r-1][c]=2;G[r-2][c]=2
    elif o[0]==1:G[r][c+1]=2;G[r][c+2]=2
    elif o[0]==2:G[r+1][c]=2;G[r+2][c]=2
    else:G[r][c-1]=2;G[r][c-2]=2
   except:0
  s=1
  for x in G:
   if'.'in x:s=0;break
 *s,='#  '
 if S:s[1]='.'
 for x in G:
  for y in x:P(s[y],end='')
  P()
def Q(G,s,e,x,y,o,a,n=0):
 c=lambda x,y:G[s[0]+x][s[1]+y]is'#'
 try:
  if c(x,y):
   try:n+=c(2*x,2*y)
   except:0
   try:n+=c(x+abs(x)-2,y+abs(y)-2)
   except:0
   try:n+=c(x-abs(x)+2,y-abs(y)+2)
   except:0
   o+=[[a,math.sqrt((s[0]+x-e[0])**2+(s[1]+y-e[1])**2),n]]
 except:0
def F(G,r,c,o,a):
 try:
  if G[r][c] is'.':o+=[a]
 except:0
def E(G,y,z,d='#'):
 c=[]
 for x in R(1,L(G)-1,2):
  n=0
  try:n+=G[x-2][y]==d
  except:0
  try:n+=G[x+2][y]==d
  except:0
  n+=G[x][y+z]==d
  if G[x][y]==d:c+=[[x,n]]
 if L(c)>1:c=T(c,key=lambda x:x[1])
 return c[0][0]

Который примерно так же бессмысленен, как и лабиринт ascii-art ...

Стоит отметить, что, поскольку случайная функция не используется до тех пор, пока не будет найден правильный путь, независимо от того, сколько раз задан один и тот же ввод, маршрут от начала до конца будет одинаковым и, пока эта программа делает работать над приведенными выше примерами, иногда он не сможет найти решение, если он, так сказать, «вбивает себя в стену».

При запуске приведенных выше примеров это дает:

>>> M('''.......
.#####.
.#####.
#######
.#####.
.#####.
.......''',True)
###############
# # #   # #   #
# # # ### # # #
# #...#.....# #
# #.#.#.###.###
#  .#.#.#...# #
###.#.#.#.### #
....#.#.#.#....
# ###.#.#.#.###
# #...#.#.#.  #
# #.###.#.#.# #
# #.....#...# #
### ####### # #
#         # # #
###############
>>> 

это:

>>> M('''..................
..................
.......####.......
......##..##......
.....##....##....#
.....#......#...##
.#############.##.
##..############..
#...###########...
#...##########....
#...##########....
#...##########....
#...##########....
....##########....
....##########....
....##########....
..................
..................''',False)
#####################################
# #     #   # # #   # #   # # # # # #
# ### ##### # # # ### # ### # # # # #
#   # # #   #   # # # #   # # #   # #
### # # ### # ### # # # ### # ### # #
# #     #   # #         # # # # # # #
# ### ##### # # ##### ### # # # # # #
# # #   #   #     # #   # # # # # # #
# # # ##### # ##### ### # # # # # # #
# # # #         # # #         #      
# # # # # # ##### # ### # ######### #
# #   # # # #   # # # # # # # # #   #
# # ####### # ### # # ### # # # # # #
#         # #           #   #     # #
### ##### # # ######### ### ### ### #
#     #   # # #   #   #     #   # # #
# ### ### # # # # # # ####### ### # #
#   # #   # # # # # # #   #       # #
# ##### # # # # # # # # # # # ##### #
#   #   # # # # # # # # #   #     # #
# ####### # # # # # # # #############
#   #     # # # # # # #         #   #
# ####### # # # # # # ##### ##### # #
#   #     # # # # # #           # # #
# ### ### # # # # # ######### ### ###
    # #   # # # # #         #   #   #
# ### # # # # # # ######### ##### ###
#   # # # # # # #                 # #
# # # ### # # # ################### #
# # # # # # # #               #     #
# ### # # # # ############# ### ### #
# # # #     #                     # #
# # ##### # # # ##### # # ##### ### #
# # #     # # #     # # #     #   # #
### ##### # ### # # # ##### # ### # #
#         #   # # # #     # #   # # #
#####################################
>>> 

и это:

>>> M('''..................
..................
.......####.......
......##..##......
.....##....##....#
.....#......#...##
.#############.##.
##..############..
#...###########...
#...##########....
#...##########....
#...##########....
#...##########....
....##########....
....##########....
....##########....
..................
..................''',True)
#####################################
#     #     # #   # # # # # # #     #
##### # # ### ### # # # # # # ### # #
# # # # # # # #     # # # # # # # # #
# # # ### # # ##### # # # # # # # ###
#   # #   # # #.......# #     #   # #
### # ### # # #.#####.# # ####### # #
#   # #   # #...#   #...#   # #   # #
### # ### # #.# # ### #.# ### ### # #
# # # # # #...# #   # #...  # #   #..
# # # # # #.# ### #######.### ### #.#
# #     #  .# #   # # #  .    # #...#
# # #######.##### # # ###.##### #.# #
#  .......#.#...........#...# #...# #
###.# ###.#.#.#########.###.# #.### #
#...# #  .#.#.#...#...#.....#...  # #
#.#######.#.#.#.#.#.#.#######.#######
#.    #  .#.#.#.#.#.#.#...#...#     #
#.#######.#.#.#.#.#.#.#.#.#.### #####
#.    #  .#.#.#.#.#.#.#.#...        #
#.#######.#.#.#.#.#.#.#.#############
#.    # #.#.#.#.#.#.#.#.....        #
#.##### #.#.#.#.#.#.#.#####.#########
#.  #    .#.#.#.#.#.#.......  # #   #
#.# # ###.#.#.#.#.#.########### # ###
..# # #  .#.#.#.#.#.........#   # # #
# # #####.#.#.#.#.#########.# ### # #
# # #    .#.#.#.#...........        #
#########.#.#.#.############### #####
#   #    .#.#.#.............# #     #
### # ###.#.#.#############.# ##### #
#     #  ...#...............      # #
##### # # ### # # # # ### # # ##### #
#     # #   # # # # #   # # #   #   #
####### # ### # # # ##### # ####### #
#       # #   # # #     # #       # #
#####################################
>>> 

Для тех, кто хотел бы попробовать запустить эту программу самостоятельно, используйте команду M(Image, Show solution). Я бы рекомендовал использовать тройные кавычки для ввода изображения, так как в противном случае будет много косых черт или символов новой строки.

Аноним Нет Лифер
источник
1
Точное прозвище: p
Fatalize
1
Хорошо сделано! Несколько советов: используйте 0вместо pass, l.append(a);l.append(b)-> l+=a,b, l.append(a)-> l+=[a], возможно, стоит присвоить '#'переменную, и def E(G,y,z):\n c=[]->def E(G,y,z,c=[]):
Loovjo
1
Также, if G[r][c]==1 or G[r][c]==2:-> if 0<G[r][c]<3:, s=[0]\n for x in R(L(I[0])*2):s+=[0]->s=[0]*(1+L(I[0])*2) и (я думаю, я еще не проверял) G=[s]-> *G=s.
Loovjo
@Loovjo Спасибо за совет except:0, l+=a,bи s=[0]*(1+L(I[0])*2)действительно помог. К сожалению, по какой-то причине назначение c в вызове функции не сбрасывает его по нескольким вызовам, что означало, что оно перестало работать, G [r] [c] может быть строкой, поэтому я не могу использовать <или> для него и * G = s дал мне синтаксическую ошибку. Тем не менее, отличный совет.
Анонимный нет,
1
@AnonymousNoLifer Нет проблем. Кроме того, еслиG[r][c] может быть строка, G[r][c]in[1,2]должно работать.
Loovjo