Codegolf — Создание Лабиринтов С Картинками

Испытание

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

Вход

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

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

I задается в следующем виде:

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

где ##################################### # # # # # # # # ### ### ### # # ##### ### ### ### # # # # # # # # # # # # # ### # ##### # ########### # ### # # # # # # # # # # # # # # ### ##### # ### ### # ### ### # # # # # # # # # # # # # # # ### # ##### ##### ### ##### # # ### # # # # # # # # # ### ####### ### ### # ### ##### ### # # # # # # # # # # # # # ### ##### # ### ####### # # # # # # # # # # # # # # # # ##### ############# ### ### ### # # # # # # # # # # # # ### # ####### # ### ### # # ### # # # # # # # # # # # # # # # ### ######### # # ##### # ##### # # # # # # # # # # # # # ##### # # ##### # ##### # # ### # # # # # # # # # # # # # # ### ### ### # ### # ##### ####### # # # # # # # # # # # # # # # ####### # ### # ##### # ### # # # # # # # # # # # # ### # # # # # ############# # ### # # # # # # # # # # # # # ##### # # ##### ####### # ### ##### # # # # # # # # # # ##### # # # # ####### # ### ######### # # # # # # # ### ######### ############# # ##### # # # # # # # # # # # ######### # ####### ####### ### # # # # # ##################################### 's are cells to be included in the solution path and .................. .................. .......####....... ......##..##...... .....##....##....# .....#......#...## .#############.##. ##..############.. #...###########... #...##########.... #...##########.... #...##########.... #...##########.... ....##########.... ....##########.... ....##########.... .................. .................. - это ячейки, которые следует исключить. Input (I): | Output: | Corresponding Cells: | | (@'s denote #'s from I) | | ....... | ############### | ############### .#####. | # # | # # .#####. | # ### ####### # | # ### ####### # ####### | # #.........# # | # #@.@.@.@.@# # .#####. | # #.#######.# # | # #.#######.# # .#####. | # #.#.......# # | # #@#@.@.@.@# # ....... | ###.#.######### | ###.#.######### | ....#.#........ | .@.@#@#@.@.@.@. | #####.#.####### | #####.#.####### | # ...#..... # | # @.@#@.@.@ # | # #.#######.# # | # #.#######.# # | # #.........# # | # #@.@.@.@.@# # | # ####### ### # | # ####### ### # | # # # # | # # # # | ############### | ############### | | 's, . Вы можете поменять местами

и символы новой строки с любым символом по вашему выбору, если они отличаются друг от друга.

В качестве альтернативы вы можете принять фактическое растровое изображение входного изображения.

Выход # 's denote walls, ############### # # # ### ####### # # #.........# # # #.#######.# # # #.#.......# # ###.#.######### ....#.#........ #####.#.####### # ...#..... # # #.#######.# # # #.........# # # ####### ### # # # # # ############### В результате лабиринт должен иметь следующий вид: # 's may be replaced by spaces if S is false. Again, characters may be swaped with other characters of your choosing or you may output an actual bitmap of the maze with the solution highlighted.

где

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

Вы можете выбрать, где расположены вход и выход.

Вы можете предположить, что правильный путь может быть сформирован из данного входного изображения.

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

Лейка пример из

Википедия

Вход:

Выход (S=ложь):

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

Выход (S=ложь):

Python 3, 1491 байт

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

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

 
 
 
 M(Image, Show solution) 
 
 
 

На это так же бессмысленно смотреть, как на лабиринт в формате ascii...

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

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

этот:

и это:

Для тех, кто хочет попробовать запустить эту программу самостоятельно, используйте команду import random;R=range;L=len;T=sorted;P=print;N=random.randint;d='#';A=abs def M(I,S): I=I.rsplit('\n');G=[[0]*(1+L(I[0])*2)for i in R(1+L(I)*2)] for i in R(L(I)):*G[1::2][i][1::2],=I[i] l=L(G[0])-2;c=E(G,l,-2);G[c][-1]=1;e=[c,l];c=E(G,1,2);G[c][:2]=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 while 1 in['.'in x for x in G]: r=N(1,L(I))*2-1;c=N(1,L(I[0]))*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,='# ' if S:s[1]='.' for x in G:P(*[s[y]for y in x],sep='') def Q(G,s,e,x,y,o,a,n=0): c=lambda x,y:G[s[0]+x][s[1]+y]is d try: if c(x,y): try:n+=c(2*x,2*y) except:0 try:n+=c(x+A(x)-2,y+A(y)-2) except:0 try:n+=c(x-A(x)+2,y-A(y)+2) except:0 o+=[[a,((s[0]+x-e[0])**2+(s[1]+y-e[1])**2)**.5,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): 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] . I would recommend using the triple-quotes to input the image since otherwise there'll be a lot of back slashes or newline characters involved.